読者です 読者をやめる 読者になる 読者になる

Live Archive 5885 - Vigenere Cipher Analysis

問題

Vigenere Cipherのルールでエンコードされた文字列C、エンコードに用いたkeyの長さの上限値K、元のテキストに含まれていた文字列W1, W2が与えられる。
len(C) <= 100000, K <= len(W1) <= 100, K <= len(W2) <= 100, K <= 100
デコードし、結果が1通りならデコードされたテキストを出力せよ。
結果が0通りもしくは2通り以上ならそれぞれ指摘せよ。
W1とW2は同時に現れ、重なっていない。

解法

keyの長さを1からKまで全て試す。
CとW1から可能性のあるkeyの集合と、CとW2から可能性のあるkeyの集合の共通部分を求める。
それらのkeyでデコードし、W1とW2が重ならずに出現するか調べる。
重ならないものは全て解の候補となり、解が何通りあるか数えればよい。
keyが異なっても解が一致する場合があるのでその時もデコードしたテキストを出力する。