九、求模式串的 next 数组

Next 数组求解：自定义演练

求 next 数组的过程，实际上是模式串 T 自己和自己进行匹配。

i 指针：代表后缀末尾。
j 指针：代表前缀末尾（同时也代表当前最长相等前后缀的长度）。

互动实验

尝试输入经典的测试用例：

ababaa (观察 j 的往复运动)
aaaaa (观察 j 的递增)
abcde (观察 j 始终归零)

模式串 (T):

提示: 尝试输入 "aaaaa" 或 "abcabc"

Step 1/15初始化：i=1 (后缀指针), j=0 (前缀指针), next[1]=0

1void get_next(String T, int next[]) {
2    int i = 1; 
3    int j = 0;
4    next[1] = 0; // 这里的下标对应逻辑位置 1
5    
6    while (i < T.length) {
7        // j==0 表示回溯到了开头
8        // T[i] == T[j] 表示前后缀匹配
9        if (j == 0 || T.ch[i] == T.ch[j]) {
10            ++i; 
11            ++j;
12            next[i] = j;
13        } else {
14            // 失配，j 回溯
15            j = next[j];
16        }
17    }
18}

1. 核心作用

当模式串的第 j 个字符失配时，从模式串的第 next[j] 个字符继续匹配。

2.图解代码

如上图所示:当第1个字符匹配失败,则令 j =0, i++, j++;此逻辑对于任何一个模式串都一样,第一个字符不匹配时,只能匹配下一个子串;因此,所有模式串的 next[ 1 ] 都写0.

如上图所示:当第2个字符不匹配时,应尝试匹配模式串的第一个字符;适用于所有模式串,next [ 2 ] 都为1得到下图:

如上图所示:现在在不匹配的位置的前边,划一根分界线;模式串一步一步往后退;知道分界线之前可以对的上;或模式串完全跨过分界线为止.

如上图所示:第3个字符不匹配时,将字符往后移;直到分界线之前可以对的上,但是上图在分界线之前对不上;所以让模式串完全跨过分界线;得到下图:

如上图所示:第4个字符不匹配,则在第4个字符前面画一个分界线;再将模式串往后移,直到字符匹配;得到下图:

如上图所示:第5个字符不匹配也是此做法;将模式串依次往后退,直到出现对应字符;得到下图:

如上图为第6个字符不匹配;按照上述方法类比;如下图:

最后得到google的next数组: ————————————————

2. 示例代码图解

以模式串 T=ababaa 为例（序号 j 从 1 开始）： | 序号 j | 1 | 2 | 3 | 4 | 5 | 6 | |--------|---|---|---|---|---|---| | 模式串 | a | b | a | b | a | a | | next[j] | 0 | 1 | 1 | 2 | 3 | 4 |

next[1] = 0：第一个字符失配时，模式串指针重置为 0，主串指针后移；
next[2] = 1：第二个字符失配时，尝试匹配模式串第一个字符；
其余 next[j]：在不匹配的位置前,划一根分界线,模式串一步一步往后退,直到分界线之前可以对的上,或模式串完全跨过分界线为止.此时 j 指向哪里, next 数组值就为多少.