目录
朴素模式匹配算法
什么是模式匹配
串的模式匹配就是在子串中找到与模式串相同的子串，并返回其所在位置。
int idex(SString S,SString T){ int k = 1; int i = k, j = 1; while(i <= S.length && j <= T.length) { if(S.ch[i] == T.ch[j]) { i++; j++; //继续比较后面字符 } else{ k++; //检查下一个子串 i = k; j = 1; } if(j > T.length) return k; else return 0; } }
为什么会出现return 0的情况，假设T为a o o,那么会出现 i 大于串的长度 ，而 j 没有超出串的长度，则跳出循环，匹配失败
朴素算法算法性能分析：
若模式串长度为m，主串长度为n，则
匹配成功的最好时间复杂度：O(m)
匹配失败的最好时间复杂度：O(n-m+1)=)(n-m)约等于O(n)
如果出现一下情况
最坏的时间复杂度是O(mn）
KMP算法
举个例子如下图，子串是google，主串是googlogooglegoolo
我们看看当我进行完前面的操作后，是否需要继续重i = 2， j = 1开始看起呢
看下面的例子
当我们发现j = 6的时候我们知道了 i 现在所指向一定不等于 e ,由于前面我们进行判断过，所以我们知道了i 不需要从 6 - 10开始匹配看，因为前面我们看过了我们不用回溯，况与 j = 1的时候比较就行。
移动之后，如果该字直接可以让i = 11的情符是 g 那么让那么i++ , j++ 。如果该字符不是 g ,那么让·i++ ，j = 1 。4
如下图
第二种情况看下面例子
如果前面几个都进行了匹配但是突然发现当 j = 5的时候与i = 9的地方不匹配，那么回溯的时候，由于前面几个进行了匹配，i 不用回到 6，7的位置，当 i 到8的位置是可以的，因为我们只能确定 i= 9的位置不等于 I ，但是我们不确定是不是 o ,所以我们可以把 i 移到 8的位置，而 j 移到 8的位置，总的来说，就是如果 j = 5发生不匹配，那么 j 回到 2，而 i 到 8。
第三种情况看下面的例子
当 j = 4与i = 6，发生了不匹配 ，i = 4与 i = 5情况由于都是 o,一定不和 g 匹配，所以跳过，应该从i = 6 开始（但是实际上，i = 6 与 g 匹配过肯定不等于 g，这个情况先不考虑）
若 j = 4 的时候发生不匹配，应该让 j = 1,i = 6 。
第四种看下面的例子
如果 i = 5的时候，与 j = 3的时候不匹配，同样的只能确定 i = 5的位置不等于o,不能确定是否等于g ，所以如果 j = 3的时候，j 退到 j = 1,而 i 的位置不变
最后一种情况
如果 j = 2的时候与 i = 4的时候不匹配，那么我们让 j = 1,i = 4。
汇总一下
我们把这些情况放到表格中去
这个表格叫next[7]
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 1 | 1 | 1 | 2 | 1 |
当 j = k ，且发现字符不匹配的时候，令 j = next[k] 来用
| g | o | o | g | l | e |
| 1 | 2 | 3 | 4 | 5 | 6 |
代码
int Index_KMP(SString S,SString T,int next[]){ int i = 1, j = 1; while(i <= S.length && j <= T.length){ if(j == 0 || S.ch[i] == T.ch[i]){ ++i; ++j; //继续比较后继字符 } else{ j = next[j]; //模式串向右移 } if(j > T.length){ //匹配成功 return i - T.lenght; } else return 0; } }
注意：
1、j = 0 的情况是由于当 j = 1的时候 next [ j ]等于0，然后 j ++，变成 j = 1,i ++ 。
2、这里面 ++ j 与 ++ i 和 j ++ 与 i ++ 效果是一样的
求模式串的next数组
看下面的例子
当 j = 6匹配失败的时候，它的next[ 6 ] = 3
在看这个情况
当 i = 7匹配失败的时候 ，让 j 指向 j = 5 的位置，所以它的next[7] = 5
在看这个例子
当 j = 5 匹配失败的时候，把字符往右移一格
同样的也可以匹配到，我们让next [5] = 4 。虽然继续往后移主串与模式串仍能匹配，我们应该选择匹配长度最大的
继续看下一种情况
当 j = 5 不匹配的时候我们应该让 next [ j ] = 1
最后在看这个例子(为什么next[1] = 0)
当 j = 1,就匹配失败的时候 我们可以让 j 设置为 0，然后 j 与 i 同时 ++
即对于任何串都可以让 next [ 1 ] = 0
总结：求模式串的next数组
如果你没看懂上面的操作，没关系，只要知道如下操作就行
串的前缀：包含第一个字符，且不包含最后一个字符的子串.
串的后缀：包含最后一个字符，且不包含第一个字符的子串.
当第 j 个字符匹配失败，由前 1 -- j - 1个字符组成的串记为S，则：next [j] = S的最长相等的前后缀长度+ 1 。
特别 next[1] = 0;
下面通过一个列子来看
当模式串为 'a b a b a a'
序号 j 1 2 3 4 5 6
模式串 a b a b a a
next [j] 0 1 1 2 3 4
j 为1的时候无可置疑的选择next[ 1 ] = 0,
j 为2的时候ab相等前缀和后缀长度都为 0 ，next [ 2 ] = 1 (0+1)
j 为3的时候aba，前缀为a，后缀为b，不相等，next [ 3 ] = 1 ( 0+1)
j 为4的时候abab，前缀为a,后缀为a的时候最长相等子串，next [4] = 2 (1+1)
j 为5的时候ababa ，当前缀为ab，后缀为ab的时候为最长相等子串，next [5] = 3 ( 2+ 1)
j 为6的时候ababaa,当前缀为aba，后缀为aba的时候为最长相等子串，next [6]= 4 (3+ 1)
求模式串T的next数组
void get_next(SString T,int next[]) { int i = 1,j = 0; next[1] = 0; while(i < T.length){ if(j ==0 || T.ch[i] == ch[j] ) { ++i; ++j; next[i] = j; } else j = next[j]; } }
上面的参考，其实也可以这样写
void get_next(String T) { int i = 1,j = 0; next[1] = 0; while(i < T.length){ if(j ==0 || T.ch[i] == ch[j] ) { next[++i] = ++j; } else j = next[j]; } }
KMP算法
int Index KMP(SSTring S,SString T){ int i = 1,j = 1; int next[T.length+1]; get_next(T,next); while(i<=S.length&&j<=T.length){ if(j==0 || S.ch[i] == T.ch[j]){ ++i; ++j; } else j = next[j]; } if(j> T.length) return i - T.length; else return 0; }
KMP算法优化
根据上面我们发现有这个情况，就是我们知道 i 指向 4 的位置 不等于g，但是我们仍有 next [ 4 ] = 1 ,继续比较了g，有点重复，所以我们可以作出优化，让next[ 4 ] = 0，j = 0 。 这样 j++,i++,让 j = 1 ， 与 i = 5 进行比较了。
nextval数组的求法
先算出next数组 先令nextva[ 1 ] = 0 for (int j = 2; j <= T.lenght; j++){ if(T.ch[next[ j ] == T.ch[j) nextval[ j ] = nextval [next [ j ] ]; else nextval [ j ] = next[ j ]; ] }
