解密加密的字符串

Question

假设有一种加密字符串的方法:

• 在字符串的末尾附加字符$,这是字母表中的第一个字符.
• 通过不断地将第一个字符移动到字符串的末尾来形成我们获得的所有字符串.
• 将我们获得的所有字符串按字母顺序排序.
• 通过将每个字符串的最后一个字符附加到其中来形成新字符串.

例如,单词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

我们可以知道原始字符串的第一个和最后一个字符,因为最右边的列是加密字符串本身,最左边的列总是按字母顺序排列.最后一个字符是加密字符串的第一个字符,因为$始终是字母表中的第一个字符,并且它只在字符串中存在一次.然后,如果我们从最右边的列中找到$字符,并在最左边的列中查找同一行上的字符,我们将得到第一个字符.

所以我们对加密字符串T $ UFIR的了解是原始字符串是F***T $,其中*是未知字符.

结束了我的想法.现在我必须利用全球网络并问另一个人:怎么样？

你可以说这是家庭作业,熟悉我的导师,我把我的赌注押在一个动态的编程问题上.

Answer 1

这是Burrows-Wheeler变换.

它是一种通常用于辅助压缩算法的算法,因为它倾向于将常见的重复短语组合在一起,并且是可逆的.

解码你的字符串:

每个字符编号:

T$UFIR
012345

现在排序,保留编号.如果字符重复,则使用索引作为辅助排序键,以便重复字符的索引按升序保持,或者使用保证此操作的排序算法.

$FIRTU
134502

现在我们可以解码.从'$'开始,并使用相关的索引作为输出的下一个字符('$'= 1,所以下一个字符是'F'.'F'是3,所以下一个字符是'R',等等...)

结果:

$FRUIT

所以只需删除标记字符,就完成了.