1

KMP 算法需要一个前缀表，以便在失败后知道它可以安全地跳过多少个字符。前缀表的一般思想是，它会告诉您对于给定模式P，在给定位置i，带有 charC的后缀有多少个公共字符，C前缀为P：

int[] T = new int[P.length()];
int i = 0;
for (int j = 1; j < P.length(); ++j) {
  if (P.charAt(j) == P.charAt(i)) {
    i++;
  } else {
    i = 0;
  }
  T[j] = i;
}

这就是我想出的。我环顾四周，实现似乎总是不同的。我尝试了几个示例（例如 ABABACA），但是我的实现和例如这个KMP 前缀表似乎都产生了相同的结果。

谁能告诉我我的实现中的逻辑错误是什么，以及在为 KMP 算法生成正确的前缀表时会失败的输入是什么？

谢谢

4

1 回答 1

1

您的算法的一个特点是表中的每个条目都比前一个条目多 0 或 1。所以挑战是找到一个字符串，其中表中的条目小于前一个条目，但不为 0。

一个这样的字符串是“ABACABABC”（来自这篇维基百科文章）。

前缀表是

{0,0,1,0,1,2,3,2,0}  from the linked answer
{0,0,1,0,1,2,3,0,0}  your proposed code
               ^------different here

感兴趣的条目是 3 后跟 2。

考虑当 7 个字符匹配时会发生什么。输入字符串看起来像

ABACABA?

在哪里？是不匹配的字符，所以？不是 B。ABA?可能是 的匹配项ABAC，因此前缀长度为 3。

现在考虑当 8 个字符匹配时会发生什么：

ABACABAB?

在哪里？不是 C。在这种情况下AB?可以匹配ABA，因此前缀长度为 2。

这表明前缀表可能有一个小于前一个条目的条目，但不是 0。

于 2018-05-09T03:43:42.807 回答