如何求字符串“ abcdeabc”的next数组？

Question

如题所述

Answer 1

对于字符串 "abcdeabc"，它的 next 数组可以通过以下步骤求得：

初始化 next[0] = -1，next[1] = 0，其中 -1 表示不存在公共前后缀。

对于 i = 2, 3, ..., 7，依次计算 next[i]：

如果 j = next[i-1] 满足 p[j] = p[i-1]，则 next[i] = j+1；

否则，如果 j > 0，则更新 j = next[j] 并回到步骤 2，否则 next[i] = 0。

按照上述步骤，可以得到字符串 "abcdeabc" 的 next 数组为：[-1, 0, 0, 0, 0, 1, 2, 3]。其中，next[0] 为边界条件，不参与匹配，next[1] 为单个字符，它的前缀和后缀为空，next[2] 为前两个字符，因为它们不相等，所以没有公共前缀和后缀，next[3] 也为 0，因为前三个字符中没有公共前缀和后缀。接下来，从 next[4] 开始，可以看到连续的 0，表示前缀和后缀不相同，然后 next[5] = 1，表示 "a" 为公共前后缀的长度为 1，next[6] = 2，表示 "ab" 为公共前后缀的长度为 2，next[7] = 3，表示 "abc" 为公共前后缀的长度为 3。