给定任意字符串，找到重复短语的有效方法是什么？我们可以说短语必须长于一定长度才能包含在内。

理想情况下，我们将获得每个短语出现的次数。

解决方案

后缀树是实现此目的的好方法。该文章的底部具有使用不同语言的实现的链接。

就像jmah所说的，我们可以为此使用后缀树/后缀数组。

这里有我们可以使用的算法的说明(请参阅第3.1节)。

我们可以在他们引用的书(Gusfield，1997年)中找到更深入的说明，该书在Google图书中。

就像早期的人们提到的那样，后缀树是完成此工作的最佳工具。我最喜欢的后缀树网站是http://www.allisons.org/ll/AlgDS/Tree/Suffix/。它在一页上列举了后缀树的所有漂亮用法，并嵌入了一个测试js应用程序以测试字符串并通过示例进行工作。

理论上

• 后缀数组是"最佳"答案，因为可以将其实现为使用线性空间和时间来检测任何重复的子字符串。但是-天真的实现实际上需要时间O(n ^ 2 log n)来对后缀进行排序，如何将其缩减为O(n log n)尚不完全清楚，更不用说O(n)了，尽管我们可以阅读相关论文，如果我们愿意的话。
• 后缀树可能比后缀数组占用更多的内存(尽管仍然是线性的)，但是更容易实现，因为我们可以在向树中添加东西时使用基数排序的想法(参见详细信息的名称)。
• KMP算法也很不错，它专门用于非常快地搜索较长字符串中的特定子字符串。如果只需要这种特殊情况，则只需使用KMP，而无需费心先建立足够的索引。

在实践中

我猜我们正在分析实际自然语言(例如英语)单词的文档，而我们实际上想对收集到的数据做些事情。

在这种情况下，我们可能只想对一些小的n(例如n = 2或者3)进行快速的n元语法分析。例如，我们可以通过去除标点符号，大写字母，和词干(运行，都运行->'run')以增加语义匹配。然后，只需构建每个相邻单词对的哈希图(例如C ++中的hash_map，Python中的字典等)到其出现的次数即可。最后，我们将获得一些非常有用的数据，这些数据的编码速度非常快，而运行起来却毫不慢。

假设我们获得了具有n个条目的排序数组A(i = 1,2,3，...，n)

Algo(A(i))
{
  while i<>n
  {
    temp=A[i];
    if A[i]<>A[i+1] then
    {     
      temp=A[i+1];
      i=i+1;
      Algo(A[i])
    }
    else if A[i]==A[i+1] then
      mark A[i] and A[i+1] as duplicates
  }
}

该算法在O(n)时间运行。