next數組如何求解
next數組示例
我們先來看兩個next數組的例子
示例1
j |
1 |
2 |
3 |
4 |
5 |
6 |
|---|---|---|---|---|---|---|
| 模式串 | a | b | c | d | e | x |
next[j] |
0 | 1 | 1 | 1 | 1 | 1 |
示例2
j |
1 |
2 |
3 |
4 |
5 |
6 |
|---|---|---|---|---|---|---|
| 模式串 | a | b | c | a | b | x |
next[j] |
0 | 1 | 1 | 1 | 2 | 3 |
求解方式
- 初始
next[1]=0，next[1]=1 j逐步遞增，在由j前面的字符組成的子串中進行查找，計算next[j]的規則爲：子串中最大對稱相等的字符個數+1
即：
PS：關於nextval數組的求解，可以參考nextval數組如何求解
求解圖示
我們以示例2中的例子進行講解
- j=2，子串爲a，無對稱子串，
next[2]=1 - j=3，子串爲ab，首尾不相等，
next[3]=1 - j=4，子串爲abc，首尾不相等，
next[4]=1 - j=5，子串爲abca，首尾相等，
next[5]=1+1=2 - j=6，子串爲abcab，前2個字符和後2個字符相等，
next[6]=2+1=3
概括來說，求解next數組的方法爲：
在由長度爲j-1的子字符串中從以下兩個方向找最長的相等字符，next數組的值爲最長的字符數+1