什么样的算法可用于查找重复的用语一个字符串？

Question

鉴于任意字符串中，什么是有效的方法寻找重复的短语?我们可以说这一短语必须超过一定的长度应包括在内。

理想的是，你最终会出现次数为每个短语。

Answer 1

喜欢早期的人们提到，后缀树是最好的工具的工作。我最喜欢的网站后缀树 http://www.allisons.org/ll/AlgDS/Tree/Suffix/.它列举了所有的漂亮的使用的后缀树木在一个页面上，有一个测试 js 应用嵌入式测试和串通过工作实例。

Answer 2

在理论上

• 一个 缀阵列 是"最好"的回答，因为它可以使用线性空间和时间来检测任何重复子.但是-天真执行实际上需要时间O(n^2日志n)排序的后缀，而且它不完全显而易见如何减少这种下降至O(n记录n)，让我们单独O(n)，虽然可以阅读有关的文件如果你想要的。
• 一个 后缀树 可以采取略有更多的存储器(仍然是线性的，虽然)，比后缀阵列，但是更容易实现建立迅速，因为你可以用的东西就像一个沙种想法作为添加的东西到树(见的链接从名称细节)。
• 的 KMP算法 也是好的要知道，这是专门用于搜索一个特定的子串在一长串的速度非常快。如果你仅仅需要这种特殊情况下，只是使用KMP并不需要费心建设一个指数的足的第一个。

在实践

我猜你是分析文件的实际自然语言(例如英国)说，和你实际上想要做一些与数据收集。

在这种情况下，你可能只是想要做一个快速的 n-gram 分析对于一些小n，例如只n=2或3。例如，可以标记你的文档进入一个清单的话，通过去除了标的资本，并制止的话(运行、运行两->"运行")，以增加语义相匹配。然后就建立一个散列地图(如hash_map在C++、字典python,等等)的各个相邻的对话，其中出现的次数为止。你到底得到一些非常有用的数据，这是非常快捷的代码，而不是疯狂的缓慢运行。

Answer 3

缀树 是一个很好的方式来实现这一点。底下的那篇文章链接，以实现在不同的语言。

Answer 4

像jmah所述，可以使用的后缀树木/后缀阵列。

有一个描述中的一个算法你可以使用 在这里， (见第3.1).

你可以找到一个更深入的说明书中，他们举(Gusfield，1997年)，这是 在谷歌的书.

Answer 5

假设你正在给定的序列A n个条目(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)的时间。