我正在阅读Suffix Arrays，构建一个的代码很简单。但是我找到的所有资源通常都使用一个简单的示例文本banana来解释这个概念。
因此，尽管示例文本很简单，并且后缀数组显示为 ( a, ana, anana, banana, na, nana)，但据我所知，这可以应用于任何类型的文本。
但我不明白，因为文本有空格、换行符、标点符号等。
那么这如何适用于任何类型的文本？
问问题
347 次
1 回答
4
对于更长的字符串，您的后缀数组如下所示：
[01] banana split, yum!
[02] anana split, yum!
[03] nana split, yum!
[04] ana split, yum!
[05] na split, yum!
[06] a split, yum!
[07] split, yum!
[08] split, yum!
[09] plit, yum!
[10] lit, yum!
[11] it, yum!
[12] t, yum!
[13] , yum!
[14] yum!
[15] yum!
[16] um!
[17] m!
[18] !
然后，您可以按字母顺序对其进行排序以找到最长的重复子字符串，这是后缀数组的常见用途。
我还记得做过类似的事情来查找长文本中单词的重复模式，我使用空格字符作为分隔符，而不是遍历每个字符：
[01] if it is true it is true
[02] it is true it is true
[03] is true it is true
[04] true it is true
[05] it is true
[06] is true
[07] true
虽然这不是一个后缀数组，但一旦按字母顺序排序，就可以找到重复的单词模式：
[01] if it is true it is true
[06] is true
[03] is true it is true
[05] it is true
[02] it is true it is true
[07] true
[04] true it is true
通过将每一行与其上一行进行比较，只要字符匹配，我们发现'is true'和'it is true'是单词的重复模式。
这种方法的灵感来自一个常见的 DNA 研究问题，称为最长重复子串问题：http ://en.wikipedia.org/wiki/Longest_repeated_substring_problem
当然，它确实出现在基因科学以外的其他领域。
于 2012-12-15T10:44:18.067 回答