设主串S='abcdefgabcad'，模式串t='abca

--- ### 1. 部分匹配表（next数组）的定义 部分匹配表的作用是记录模式串 t 中每个位置 j 之前的最长相等前缀和后缀的长度。具体来说，对于模式串 t = t0 t1 t2 ... t(m-1)，next[j] 表示子串 t[0:j-1] 的最长相等前缀和后缀的长度。 --- ### 2. 模式串 t = 'abcad' 的部分匹配表计算 我们逐步计算模式串 t = 'abcad' 的部分匹配表。 #### 初始化 - j = 0：next[0] = -1（表示模式串的开头，没有前缀和后缀） - j = 1：next[1] = 0（单个字符，没有前缀和后缀） #### 计算过程 - j = 2：子串 t[0:1] = 'ab' - 前缀：'a' - 后缀：'b' - 最长相等前缀和后缀的长度为 0。 - next[2] = 0 - j = 3：子串 t[0:2] = 'abc' - 前缀：'a', 'ab' - 后缀：'c', 'bc' - 最长相等前缀和后缀的长度为 0。 - next[3] = 0 - j = 4：子串 t[0:3] = 'abca' - 前缀：'a', 'ab', 'abc' - 后缀：'a', 'ca', 'bca' - 最长相等前缀和后缀是 'a'，长度为 1。 - next[4] = 1 - j = 5：子串 t[0:4] = 'abcad' - 前缀：'a', 'ab', 'abc', 'abca' - 后缀：'d', 'ad', 'cad', 'bcad' - 最长相等前缀和后缀的长度为 0。 - next[5] = 0 --- ### 3. 部分匹配表（next数组）的最终结果 对于模式串 t = 'abcad'，部分匹配表如下： j | 0 | 1 | 2 | 3 | 4 | 5 | next[j]| -1| 0 | 0 | 0 | 1 | 0 | --- ### 4. 失配时的回溯 当 i = j = 3 时发生失配，即 S[3] = 'd' 与 t[3] = 'a' 不匹配。此时： - 根据部分匹配表，next[3] = 0。 - 因此，j 会回溯到 0，而 i 保持不变。 --- ### 5. 最终答案 下次开始匹配时： - i = 3（主串指针不变） - j = 0（模式串指针回溯到 0）