1184 - 暗号理論入門：換字式暗号

時間制限 0.5 秒 / メモリ制限 32 MB / 得点 1 / Writer r1825 / x 2 / 統計 /

TLE
0.5sec
MLE
32MB
得点
1

Aphorismus

ヒトの代わりに考える機械をつくることはできない。
── アラン・チューリング

問題

換字式暗号(かえじしきあんごう)は原始的な暗号の一つです。
例えば、 

Apple
とあった時に 
Vqqic

などとします。
この時、A->V, p->q, l->i, e->c というように置き換えました。
このように文字を置き換えることで暗号化するアルゴリズムを換字式暗号と言います。
換字は「かんじ」と発音したいところですが、「かえじ」と発音するのが一般的です。
これは漢字などと同じ発音だと紛らわしいためです。

さて、先ほどの例のように一対一対応された換字式暗号(単純換字)は非常に単純です。そのため解読も容易にできます。
単純換字に効果的な解読法に頻度解析というものがあります。その名の通り文字の出現頻度を基にして解読を試みます。
例として、次の暗号化された英文について考えてみましょう。 

ytr ewqraydfr lg ytr weahnaj kra
暗号化されているので当然読むことはできません。
ここで各文字の出現回数を見てみましょう。

aaaadeefghjklnqrrrrrttwwyyy
r 5回
a 4回
y 3回

上位3つを挙げました。 ところで英語の文章に最も出てくるアルファベットは何だと思いますか。
これは一般にeであることが知られています。
その後t, a, o, i, n, ...と続いていきます。
そこで出現回数が一番多い文字をeと置換してみましょう。
みやすくするため、置換後の文字は大文字にします。 

ytE ewqEaydfE lg ytE weahnaj kEa

ytEに注目しましょう。
英文で最も出現頻度が多い単語はtheです。
y=T, t=Hと仮定して置換してみると、 

THE ewqEaTdfE lg THE weahnaj kEa

それらしいものができました。
次に4回登場しているaを置換しましょう。

THE ewqEATdfE lg THE weAhnAj kEA // a->A

THE ewqEOTdfE lg THE weOhnOj kEO // a->O

THE ewqEITdfE lg THE weIhnIj kEI // a->I

THE ewqENTdfE lg THE weNhnNj kEN // a->N

aを出現頻度の高い文字にそれぞれ置換しました。
2単語目に注目して、それぞれのパターンを電子辞書でワイルドカード検索すると、

ewqEATdfE 該当なし
ewqEOTdfE videotape
ewqEITdfE 該当なし
ewqENTdfE 該当たくさん

videotapeであるとは考えにくいので(e->v, w->iと置換すると5単語目がivn...となる)
a=Nと考えましょう。

THE ewqENTdfE lg THE weNhnNj kEN

ewqENTdfEに着目して再び電子辞書で調べると次のような候補が上がりました。

  • adventure

先ほど「該当たくさん」と書いたのに一つしかありません。
手持ちの電子辞書で「???ent??e」と調べていただくとわかると思いますが、
このように検索するとたくさんの候補があがります。
しかしこの?には同じアルファベットは入りません。ewqENTdfEの仮定されていないアルファベット(=小文字)は全て異なるためです。
そのため?に同じアルファベットがあるとadventure以外の単語は除外されます。
ですのでそのように置換すると、 

THE ADVENTURE lg THE DANhnNj kEN

DANhnNjも同様に電子辞書で検索するとdancingしか出てきませんのでそれを採用しましょう。

THE ADVENTURE lg THE DANCING kEN

ほぼ全体像が見えてきましたね。
ここまでくると大概の人がどのような英文なのかは分かっていると思いますが、一応最後までやりましょう。

googleで
THE ADVENTURE THE DANCING EN
と検索するとthe adventure of the dancing menというのが出てきます。
文字数的にも使われているアルファベット的にも、問題的にもこれが答えそうです。

よって、 

ytr ewqraydfr lg ytr weahnaj kra

を解読すると

the adventure of the dancing men

になりました。
実際はもっと多い文章を解読するため、情報量が多くより論理的に解読することができます。
ちなみにthe adventure of the dancing menは日本語で『踊る人形』というシャーロックホームズシリーズの小説のタイトルです。
そしてその中に「踊る人形」という有名な暗号が登場しますがそれも単純換字の暗号です。

さて、すべて英小文字の空白を含まない文字列Sが与えられます。
その後26個の英小文字のアルファベットc1からc26が与えられます。
Sはaがc1、bがc2、...、zがc26に置換された単純換字の暗号文です。
これを平文(暗号化されていない文)に戻してください

入力

S
c1
...
c26

出力

ans

制約

Sの文字数は1以上$10^6$以下
ciは相異なる

テストケース

例1

入力

neqcvtz
r
t
p
o
a
l
k
u
v
y
f
h
x
j
q
m
s
c
n
w
z
d
i
g
e
b

出力

syoribu