第四章串

4.1 串

提示：KMP算法

我们可以用一个简单的流程来解释这个算法：令主串'S'为：ABC ABCDAB ABCDABCDABDE；令子串'W'为：ABCDABD；令'm'为主串字符串位数，令'i'为子串字符串位数；
第一轮：

S[3] != W[3]且前缀{A,AB}与后缀{C,CB}不同，故令m = 4, i = 0，继续比较；
第二轮：

S[10] != W[6]但前缀{A,AB,ABC,ABCD,ABCDA}与后缀{B,AB,DAB,CDAB,BCDAB}有最长相等前后缀长度为2，故接下来从S[8]开始比较，令m = 8, i = 0继续比较；
第三轮：

S[10] != W[2]且前缀{A}与后缀{B}不同，故令m = 11, i = 0，继续比较；
第四轮：

S[17] != W[6]且前缀{A,AB,ABC,ABCD,ACBDA}与后缀{B,AB,DAB,CDAB,BCDAB}有最长相等前后缀长度为2，故接下来从S[15]开始比较，令m = 15, i = 0继续比较；
第五轮：

S[21] == W[6]比较完成，其起始位置在S[15]。

例

设有字符串S = 'abbaabaabaac', P = 'aabaac'; 1⃣ 求P的next数组。2⃣ 若S作为主串，P作为模式串，试给出KMP的匹配过程。
【解】 1⃣ 步骤一：通过前缀、后缀求出字符串的部分匹配值（PM） 'a'的前缀和后缀都是空集，最长相等前后缀长度0； 'aa'的前缀为{a}，后缀为{a}，最长相等前后缀长度1； 'aab'的前缀为{a,aa}后缀为{b,ab}，最长相等前后缀长度0； 'aaba'的前缀为{a,aa,aab}后缀为{a,ba,aba}，最长相等前后缀长度1； 'aabaa'的前缀为{a,aa,aab,aaba}后缀为{a,aa,baa,abaa}，最长相等前后缀长度2； 'aabaac'的前缀为{a,aa,aab,aaba,aabaa}后缀为{c,ac,aac,baac,abaac}，最长相等前后缀长度0；故字符串P的部分匹配值为：010120；步骤二：根据PM计算next数组：首个为0，填入前一个序号的PM值加一，即next[i] = PM[i-1]+1；

模式串 a a b a a c
序号 1 2 3 4 5 6
PM 0 1 0 1 2 0
next 0 1 2 1 2 3

2⃣ KMP匹配过程：

主串 a a b a a b a a b a a c
第一次比较 a a b a a c
第二次比较 a a b a a c
都三次比较 a a b a a c
- 第一次匹配：从主串和子串的第一个字符开始比较，i = 6 ,j = 6时失败；
- 第二次匹配：next[6] = 3，主串当前位置和子串的第三个字符比较，i = 9, j = 6 时失败；
- 第三次匹配：next[6] = 3，主串当前位置和子串的第三个字符比较，匹配成功。