字符串
前缀：除过最后一个字符以外，字符串的所有头部字串；
后缀：除过第一个字符以外，字符串的所有尾部字串；
部分匹配值：字符串的前缀和后缀的最长相等前后缀长度
例：’ababa’
‘a’ 前缀：空集 后缀：空集 前缀⋂后缀=空集 最长相等前后缀长度：0
‘ab’ 前缀：{a} 后缀：{b} 前缀⋂后缀=空集 最长相等前后缀长度：0
‘aba’ 前缀：{a,ab} 后缀：{a,ba} 前缀⋂后缀={a} 最长相等前后缀长度：1
‘abab’ 前缀：{a,ab,aba} 后缀：{b,ab,bab} 前缀⋂后缀={ab} 最长相等前后缀长度：2
‘ababa’ 前缀：{a,ab,aba,abab} 后缀：{a,ba,aba,baba} 前缀⋂后缀={a,aba} 最长相等前后缀长度：3
所以字符串部分匹配值：00123。
下面以’abcac’为例：
‘abcac’
‘a’ 空 空 0
‘ab’ {a} {b} 0
‘abc’ {a,ab} {c,bc} 0
‘abca’ {a,ab,abc} {a,ca,bca} 1
‘abcac’ {a,ab,abc,abca} {c,ac,cac,bcac} 0
即00010
| 编号 | 1 | 2 | 3 | 4 | 5 |
| S | a | b | c | a | c |
| PM(部分匹配值) | 0 | 0 | 0 | 1 | 0 |
使用pm表来匹配的过程：
| 主串 | a | b | a | b | c | a | b | c | a | c | b | a | b |
| 子串 | a | b | c |
在此处，c与a不匹配，计算需要移动的位数，此处对应的匹配值为最后一个匹配字符对应的匹配值。
移动位数=已匹配的字符数-对应的部分匹配值
此处：2-0=2
| 主串 | a | b | a | b | c | a | b | c | a | c | b | a | b |
| 子串 | a | b | c | a | c |
不匹配，4-1=3
| 主串 | a | b | a | b | c | a | b | c | a | c | b | a | b |
| 子串 | a | b | c | a | c |
匹配成功。
改进：
move=(j-1)-PM[j-1]
即PM表右移一位，注意：
右移产生的空缺用-1填充，因为如果第一个就匹配失败，需要将子串右移一位，而不需要计算子串移动的位数
| 编号 | 1 | 2 | 3 | 4 | 5 |
| S | a | b | c | a | c |
| PM(部分匹配值) | 0 | 0 | 0 | 1 | 0 |
| next | -1 | 0 | 0 | 0 | 1 |
最后一个元素右移过程中发生了溢出，因为最后一个元素的部分匹配值供下一个使用，不存在，所以可以舍去。
可以改为：move=(j-1)-next[j]
相当于子串比较指针j回退到
j=j-move=j-((j-1)-next[j])=next[j]+1
为了简洁计算方便，将next数组整体加1
| 编号 | 1 | 2 | 3 | 4 | 5 |
| S | a | b | c | a | c |
| PM(部分匹配值) | 0 | 0 | 0 | 1 | 0 |
| next[j] | 0 | 1 | 1 | 1 | 2 |
next[j]的含义为：在子串第j个字符与字串发生失配时，则跳转到子串的next[j]位置重新与字串当前位置比较。
kmp进一步优化
模式’aaaab’与主串’aaabaaaab’匹配
‘aaaab’
‘a’ 空 空 0
‘aa’ {a} {a} 1
‘aaa’ {a,aa} {a,aa} 2
‘aaaa’ {a,aa,aaa} {a,aa,aaa} 3
‘aaaab’ {a,aa,aaa,aaaa} {b,ab,aab,aaab,} 0
PM：0，1，2，3，0，
右移：-1，0，1，2，3，
加1：0，1，2，3，4，
nextval:
相同的再次比较毫无意义，所以在p[j]=p next[j]时，将next[j]修正为next[next[j]]，直到两者不相等为止。
void get_nextval(SString T,int nextval[j]){
int i=1,j=0;
nextval[1]=0;
while(i<T.length){
if(j==0||T.ch[i]T.ch[j]){
i++;++j;
if(T.ch[i]!=T.ch[j]) nextval[i]=j;
else nextval[i]=nextvaal[j];
}
else j=nextval[j];
}
}| 主串 | a | a | a | b | a | a | a | a | b |
| 模式 | a | a | a | a | b | ||||
| j | 1 | 2 | 3 | 4 | 5 | ||||
| pm | 0 | 1 | 2 | 3 | 0 | ||||
| next[j] | 0 | 1 | 2 | 3 | 4 | ||||
| nextval[j] | 0 | 0 | 0 | 0 | 4 |
解法1
下面两题位序应该从0开始计算，为了方便计算，从1开始
例：2019年统考
设主串T=’abaabaabcabaabc’,模式串S为=’abaabc’,采用KMP算法进行模式匹配，到匹配成功为止，在匹配过程中进行的单个字符间的比较次数是（b）
a.9 b.10 c.12 d.15
解：’abaabc’
‘a’ 空 空 0
‘ab’ ‘a’ ‘b’ 0
‘aba’ ‘a,ab’ ‘a,ba’ 1
‘abaa’ ‘a,ab,aba’ ‘a,aa,baa’ 1
‘abaab’ ‘a,ab,aba,abaa’ ‘b,ab,aab,baab’ 2
‘abaabc’ ‘a,ab,aba,abaa,abaab’ ‘c,bc,abc,aabc,baabc’ 0
pm:0,0,1,1,2,0
右移：-1,0,0,1,1,2
加1： 0,1,1,2,2,3
nextval:
| a | b | a | a | b | c | |
| next[j] | 0 | 1 | 1 | 2 | 2 | 3 |
| nextval | 0 | 1 | 0 | 2 | 1 | 3 |
| 主串 | a | b | a | a | b | a | a | b | c | a | b | a | a | b | c |
| 模式串 | a | b | a | a | b | c | |||||||||
| a | b | a | a | b | c |
所以比较10次
例：2015年统考
已知字符串S为’abaabaabacacaabaabcc’，模式串t为’abaabc’，采用KMP算法进行匹配，第一次出现失配（s[i]≠t[j]）时，i=j=5，则下次开始匹配时，i与j的值分别是（c）
a.i=1,j=0 b.i=5,j=0 c.i=5,j=2 d.i=6,j=2
解：’abaabc’
‘a’ 0
‘ab’ 0
‘aba’ 1
‘abaa’ 1
‘abaab’ 2
‘abaabc’ 0
pm:001120
右移:-1,0,0,1,1,2
加1:0,1,1,2,2,3
nextval :
| a | b | a | a | b | c | |
| PM | 0 | 0 | 1 | 1 | 2 | 0 |
| next | -1 | 0 | 0 | 1 | 1 | 2 |
| next | 0 | 1 | 1 | 2 | 2 | 3 |
| nextval | 0 | 1 | 0 | 2 | 1 | 3 |
| a | b | a | a | b | a | a | b | a | c | a | c | a | a | b | a | a | b | c | c |
| a | b | a | a | b | c | ||||||||||||||
| a | b | a | a | b | c |
开始时:i=6,j=3
i=5,j=2
解法2
例：
任何字符串，next[1]直接写0
next[2]直接写1
在不匹配的位置前边，画一条分界线，模式串一步一步往后退，知道分界线之前能对上或者模式串完全跨过分界线为止，此时j指向哪，next数值就是多少
‘ababaa’
| a | b | a | b | a | a | |
| next | 0 | 1 | 1 | 2 | 3 | 4 |