我需要在线性时间内执行一个著名的Burrows-Wheeler变换。我找到了一个带有后缀排序和 EOF 字符的解决方案，但附加 EOF 会更改转换。例如：考虑字符串bcababa和两次旋转
- s1 =
abababc - s2 =
ababcab
很明显，S1
- S1 = ABABA#BC
- S2 = ABA#BCAB
现在是 S2
您可以通过计算与自身连接的字符串的后缀数组，在没有 EOF 字符的情况下线性时间和空间中执行转换。 然后迭代后缀数组。 如果当前后缀数组值小于 n ，则将从后缀数组中当前值表示的位置开始的旋转的最后一个字符添加到输出数组中。但是，此方法将产生略有不同的 BWT 转换结果，因为字符串旋转不会像存在 EOF 字符那样排序。
更全面的描述可以在这里找到：http://www.quora.com/Algorithms/How-I-can-optimize-burrows-wheeler-transform-and-inverse-transform-to-work-in-O-n-time-O-n-space
您需要在字符串中包含 EOF 字符才能使 BWT 正常工作，因为否则您将无法执行逆变换来取回原始字符串。如果没有 EOF，两个字符串 "ba" 和 "ab" 都有相同的转换版本("ba"(。使用 EOF，转换是不同的
ab ba
a b | a | b
b | a b a |
| a b | b a
即 ab 转换为 "|ab"，ba 转换为 "b|a"。
BWT 需要 EOF，因为它标志着角色周期的开始点。
回复：根据维基百科，在没有EOF字符的情况下执行此操作，
由于输入字符串的任何旋转都会导致相同的 转换后的字符串，如果不添加"EOF"，则无法反转 BWT 标记到输入，或者用信息增强输出，例如 作为索引，这使得可以从 其所有旋转的类。
变换有一个双射版本，通过它 转换后的字符串唯一标识原始字符串。在此版本中， 每个字符串都有一个相同长度的唯一逆函数。
双射变换是通过首先将输入分解为 林登单词的非递增序列;存在这样的因式分解 由陈-福克斯-林登定理，并可以在线性时间中找到。 然后，该算法将所有这些旋转排序在一起 的话;与通常的Burrows-Wheeler变换一样，这会产生一个 N 个字符串的排序序列。然后获得转换后的字符串 通过在此排序中选取每个字符串的最后一个字符 列表。
这个线程很旧，但我遇到了同样的问题，并提出了以下解决方案：
- 找到字典编纂的最小字符串旋转并保存偏移量(需要反转((我使用 lydon 分解(
- 在旋转的字符串上使用正常的 bwt 算法(这会产生正确的输出，因为所有算法都认为字符串后跟字典上的最小字符(
- 反转：取消bwt，例如从索引0开始向后搜索，并将腐蚀字符写入保存的偏移量