algorithm - 更简单的 KMP 前缀表构建。这个实现会有什么问题？

Question

KMP 算法需要一个前缀表，以便在失败后知道它可以安全地跳过多少个字符。前缀表的一般思想是，它会告诉你对于给定的模式 P，在给定的位置 i 有一个字符 C， 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 prefix table似乎产生相同的结果。

任何人都可以告诉我我的实现中的逻辑错误是什么，以及在为 KMP 算法生成正确的前缀表时使用什么样的输入会失败？

谢谢

Answer 1

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

一个这样的字符串是“ABACABABC”(来自 this wikipedia article )。

前缀表是

{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。