一.模式匹配算法
(一)基础
不一致。 与以下子字符串进行比较
成功或直到最后都没有找到
(二)进阶
1 .假设主串的长度为n，则长度为m的部分串共有n-m 1个，因此最大比较次数n-m 1
2 .代码原理
I和j同时向后移动，一个个比较匹配是否成功
此时i=6=j
在第六个位置匹配失败了。 继续重新比较下一个子字符串
移动指针：
i=i-j 2 (现在I指2 ) ) ) ) ) )。
j=1
直到结束
此时，I和j指向的字符一直相等，不断向后移动，当j超过图案列的长度(T.length )时匹配成功
3 .代码实现
intindex(sstrings，SString T ) {int i=1，j=1； while(I=s.Lengthj=t.Length ) if ) s.ch[I]==t.ch[j] ) I； j； }else {i=i - j 2； j=1； }if(jt.Length ) return i - T.length； elsereturn 0； )4.时间复杂性
主串长度为n，图案串长度为m，一般为nm
最差： o((n-m1 ) m )=o (nm ) ) ) ) ) ) ) )。
最佳： O(N-M1 )=o (n ) ) ) ) ) ) ) ) )。
2.kmp算法
如果1-5匹配成功，则6匹配失败
可以看到1-5是abaab
也就是说
此时i=j=6
后移比较，后两次比较明显匹配失败
(2-1失败)
(4-2失败)
再次向后移动进行比较，你知道此时需要继续探索吗？ 获取的数据，直接比较6-3即可。
为了提高效率，省略了第二次明显失败的比较，直接跳到这里，使I指向6，j指向3
也就是说
在这种情况下，i=6，j=3
元： i=6，j=6
可以看到，在前五次匹配失败后，通过保持I指针的位置，并将j指针指向3，可以更高效。 这就是KMP算法
(原本i=j=6，第五次匹配失败时)
以上是第五次匹配失败的情况，我们来探究一下其他情况吧
1.4匹配失败
此时i=j=4
跳过
(2-1失败)
继续向后移动
在这种情况下i=4，j=2
本来i=4=j
也就是说，第四次匹配失败后，下次比较： I不变，j移动到2
2.第三次匹配失败
此时i=j=3
跳过
(2-1失败)
继续向后移动
这种情况下i=3，j=1
原本： i=3=j
也就是说，在第三次匹配失败之后，在下次比较中，I不变，j移动到1
3 .第二次匹配失败
此时i=j=2
继续向后移动
这种情况下i=2，j=1
也就是说，在第二次匹配失败之后，在下次比较中，I不变，j移动到1
4.第一次匹配失败
此时i=j=1
继续向后移动
为了方便，j=0，然后I和j同时变为1
也就是说，第一次匹配失败后，下次比较： j=0，I，j
可知，法则(指针的移动)的导出由模式列决定，与主列无关，因此该法则对于相同的模式列在所有匹配中是共同的
KMP算法中主串指针i是不回溯的，而朴素模式匹配算法中i需要回溯
用next数组表示这个。 next数组也只与模式列有关，与主列无关
next[i]表示第I个元素匹配失败
【导线安装】
intindex_kmp(sstrings，SString T，int next[] ) next数组int i=1，j=1； 如果while(I=s.Lengthj=t.Length ) if ) j==0||s.ch[I]==t.ch[j] ) /相等，则继续进行比较，如果j=0，则同时输入I； j； }elsej=next[j]； //匹配失败，j按照next数组移动，I不变(j=0时为上) (if ) jt.length ) return i - T.length； //成功匹配，并返回主字符串中子字符串的位置(第一个字符位置) elsereturn 0； //匹配失败(【效率分析】)
设主串长度为n，图案串长度为m
求出next数组的时间复杂度o(m )
模式匹配处理最差时间复杂度o(n ) ) ) ) ) ) ) ) )。
因此KMP算法时间复杂度O(m+n)
【求出next序列】
1 .在前面的分析中，对于任意的模式列，如果第一个要素的匹配失败，则j=0，然后将I和j一起向后移动，所以j为0的位置，next[1]=0成立
2 .如果第二个元素匹配失败，模式列向后移动一次，http://www.Sina.com/http://www.Sina.com /
其他同上
【练习】
【解析】在KMP算法中，为了使表达式更简单，如果字符串的位顺序从1开始，则next数组必须整体加1； 如果字符串的位顺序从0开始，则next数组不需要整体加1。 本问题的选项全部从-1开始，字符串的位序从1开始，表示整个next数组中加1
【答案】c