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

Question

是否有任何算法可用于查找字符串中最常见的短语(或子字符串)？例如，以下字符串会将“hello world”作为其最常见的双词短语:

“hello world 这是 hello world。hello world 在这个字符串中重复了三次!”

在上面的字符串中，最常见的字符串(在重复无限次的空字符串字符之后)是空格字符 。

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

Answer 1

这是类似于 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 来计算同一字符串的自相似匹配数也很简单。使用普通字符串和普通最小长度，只有少量表格单元格将通过此映射进行处理。

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