串的模式匹配算法
子串的定位操作通常称做串的模式匹配，这也是串的一个很要的操作。
一，一般定位子串位置算法
算法基本思想：从主串的第1个字符起和模式的第一个字符进行比较，若相等，则再比较主串和模式串的后续字符。否则将主串的后续字符和模式串的第一个字符进行比较，在网上找的一张图片：
算法分析
2.1 主串的第i个字符接下来与模式串的哪个字符进行比较
假设模式和主串正在比较第K个字符，那么前面K-1个字符必然已经比较成功，也就是满足这个关系：
这里所要表达的意思就是：若模式串中存在满足上面3中条件的两个子串，则当匹配过程中，主串中第i人字符与模式中第j个字符比较不相等时，只需要将模式向右移动至模式中第k个字符和主串中第i个字符对齐，因为模式串中的头k-1个字符肯定与主串中的第i个字符 之前的k-1个字符相等，所以，匹配只需要从模式中第k个字符与主串中第i个字符比较，就可以进行后续比较操作。我们定义若模式串中第j个字符不相等，然后从第k个字符开始比较这种关系，即next[j] = K .
2.2 next[j] = K 求解
next[j] 的定义如下【这是数据结构书籍上的定义】
假定下标从1开始。
假设next[j]=k,这表明存在"P1…Pk-1”=“Pj-k+1…Pj-1"这样的关系，此时next[j+1]的值如何计算呢？分下面两种情况：
1）若Pk=Pj，则有“P1…Pk-1Pk”=“Pj-k+1…Pj-1Pj” ，如果在j+1发生不匹配，说明next[j+1] = k+1 = next[j]+1。
2) 若Pk≠Pj，可把求next值问题看成是一个模式匹配问题，整个模式串既是主串，又是子串:
(1)若Pk’=Pj，则有“P1…Pk’”=“Pj-k’+1…Pj”，next[j+1]=k’+1=next[k]+1=next[next[j]]+1.
(2)若Pk”=Pj ，则有“P1…Pk””=“Pj-k”+1…Pj”，next[j+1]=k”+1=next[k’]+1=next[next[k]]+1.
......
(n)当无任何k'满足等式时，next[j+1]=1.
int index_kmp(Stirng S,String T,int pos){int i=pos;int j=1;while(i<=S.length && j<=T.length){if(j==0 || S[i] == T[j]) {i++;j++;}else{j=next[j];}if(j>T.length) return i-T.length;elsereturn 0;}可以看到这和一般的匹配算法，有两个区别：1）匹配失配后，主串不是重新回溯，而是将子串往右滑动，以找到一个合适的点，再进行比较。
2）当比较字符成功或者是包含当前位置的子串不存在时，将主串移至下一个位置。
