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

Question

KMP 算法需要一个前缀 table，以便在失败后知道它可以安全地跳过多少个字符。前缀 table 的一般思想是，它会告诉你对于给定的模式 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 算法生成正确的前缀 table？

谢谢

Answer 1

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

其中一个字符串是 "ABACABABC"（来自 this wikipedia article）。

前缀table是

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

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

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

Simpler KMP prefix table building. What would be wrong with this implementation?

algorithm

knuth-morris-pratt