查找字符串中最常见的子字符串的算法

是否有任何算法可用于查找字符串中最常见的短语（或子字符串）？例如，以下字符串将“hello world”作为其最常见的两个单词短语：

"hello world this is hello world. hello world repeats three times in this string!"

在上面的字符串中，最常见的字符串（在空字符串字符之后，重复无限次）将是空格字符.

有什么方法可以生成此字符串中的常见子字符串列表（从最常见到最不常见）？

这是类似于 Nussinov 算法的任务，实际上甚至更简单，因为我们不允许对齐中出现任何间隙、插入或不匹配。

对于长度为N的字符串A，定义一个F[-1 .. N, -1 .. N]表并按照以下规则填写：

  for i = 0 to N
    for j = 0 to N
      if i != j
        {
          if A[i] == A[j]
            F[i,j] = F [i-1,j-1] + 1;
          else
            F[i,j] = 0;
        }

例如，对于B A O B A B:

这运行在O(n^2)时间。表中的最大值现在指向最长自匹配子序列的结束位置（i - 一次出现的结束，j - 另一次出现的结束）。一开始，假设数组是零初始化的。我添加了条件来排除最长但可能不有趣的自匹配对角线。

再想一想，这个表在对角线上是对称的，所以只需要计算它的一半就足够了。此外，该数组是零初始化的，因此分配零是多余的。剩下的就是

  for i = 0 to N
    for j = i + 1 to N
      if A[i] == A[j]
         F[i,j] = F [i-1,j-1] + 1;

更短但可能更难理解。计算表包含所有匹配项，无论是短匹配还是长匹配。您可以根据需要添加进一步的过滤。

在下一步中，您需要恢复字符串，从非零单元格开始向左沿对角线排列。在此步骤中，使用一些哈希图来计算同一字符串的自相似匹配数也很简单。对于正常字符串和正常最小长度，只有少量表格单元格将通过此映射进行处理。

我认为直接使用 hashmap 实际上需要 O(n^3)，因为访问结束时的关键字符串必须以某种方式进行比较以确保相等。这种比较可能是 O(n)。