文字列を暗号化する特定の方法があるとしましょう。
- 文字列の最後に、アルファベットの最初の文字である文字$を追加します。
- 最初の文字を文字列の最後に連続的に移動して、取得したすべての文字列を形成します。
- 取得したすべての文字列をアルファベット順に並べ替えます。
- 各文字列の最後の文字を追加して、新しい文字列を作成します。
たとえば、FRUITという単語は次のように暗号化されます。
We append the character $ at the end of the word:
FRUIT$
We then form all the strings by moving the first character at the end:
FRUIT$
RUIT$S
UIT$FR
IT$FRU
T$FRUI
$FRUIT
Then we sort the new strings into alphabetical order:
$FRUIT
FRUIT$
IT$FRU
RUIT$F
T$FRUI
UIT$FR
The encrypted string:
T$UFIR
今私の問題は明らかです:与えられた文字列を元の形式に復号化する方法。
半週間頭をドキドキさせていて、ようやく紙切れになりました。
どうすればこれを続けることができますか?
私が発見したこと:
暗号化の最後のステップがある場合:
$FRUIT
FRUIT$
IT$FRU
RUIT$F
T$FRUI
UIT$FR
右端の列は暗号化された文字列自体であり、左端の列は常にアルファベット順になっているため、元の文字列の最初と最後の文字を知ることができます。$は常にアルファベットの最初であり、文字列に1回しか存在しないため、最後の文字は暗号化された文字列の最初の文字です。次に、右端の列から$文字を見つけ、左端の列の同じ行でその文字を検索すると、最初の文字が取得されます。
したがって、暗号化された文字列T $ UFIRについて知ることができるのは、元の文字列がF *** T $であるということです。ここで、*は不明な文字です。
これで私の考えは終わりです。今、私はワールドワイドウェブを利用して、別の人間に尋ねなければなりません:どうやって?
これは宿題だと言えます。私の家庭教師に精通しているので、これが動的計画法の問題であることに賭けます。