串的模式匹配算法
子串的定位操作通常称为串的 模式匹配，其中T称为 模式串。
一般的求子串位置的定位函数（Brute Force）
我写java的代码是这样的
){char[] s_arr = S.toCharArray();char[] t_arr = T.toCharArray();int i,j,k;//i是主串S的指针，j是模式串的指针if(pos < 0 || pos>S.length() ||S.length() < T.length() || pos+T.length()>S.length())return -2;/*最外层是与主串匹配的最多次数，从数组下标为0开始匹配，i表示当前匹配是从主串下标为i的元素开始的*/for(i = pos-1;i < S.length()-T.length();i++){/*内层循环是模式串的循环，，j表示当前匹配指针的位置*/for(j=0;j<T.length();j++){/*i+j是主串上指针的位置，如果两者不匹配，则将主串的指针挪后一个位置，模式串指针从头开始，重新匹配*/if(s_arr[i+j] != t_arr[j]){break;}}/*与模式串的匹配结束，判断模式串的指针位置*/if(j>=T.length())return i;}return -1;}
书上的算法是这样的(伪码)
int index(String S,String T,int pos){/*返回子串T在主串S中第pos位置字符后的位置，若不存在，返回值为0其中T非空，1<=pos<=S.length，S[0]和T[0]位置存储字符串长度*/i = pos;j = 1;while(i <= S[0] && j <= T[0]){if(S[i] == T[j]){i++;j++/*两个串的指针后退*/}else{i = i-j+2;j = 1;/*主串的指针后退i-j+2个单位，由于下标从1开始主串中j-i+1的位置与模式串1位置对应，再向后挪一个单位得。*/}}if(j>T[0])return i-T[0];return 0}
当主串长度为m，模式串长度为n时（m>n），BF的时间复杂度O(m*n)。
改进后的模式匹配算法
由于在BF算法中，每一次和主串匹配过程中遇到不配字符后，模式串指针总是要回溯到一开始重新和主串的下一个字符开始匹配，期间可以利用以及得到的“部分匹配”结果，将模式串“向右滑动”一段尽可能远的距离，继续比较。其实还是将当前主串的指针所指的字符，与模式串中“部分匹配”的内容中某一个字符继续匹配。 现在的问题就变成了： * 当前主串所指的字符，应该模式串中完成“部分匹配”的子字符串中哪一个字符继续比较，即向右滑动的距离。
主串S下标 1，2，…，i-j+1，…，i-1，i，…，m
模式串T下标 1，…，j-1，j，…，n
当前指针i和j所指的字符在进行匹配（未判断二者是否相等）。
这样的情况下有这样的等式：s(i+j-1)…s(i-1) = t(1)…t(j-1),是对应匹配的。
那么假设s(i)和t(j)不匹配，模式串需要右移，右移动后，此时s(i)和t(k)正在匹配（这里的k是假设出来的）
有这样的等式:s(i-k+1)…s(i-1) = t(1)…t(k-1)
形象的描述
S : a a b a b c d e i指向cT1: a b a b ej指向eT2:a b a b e 右移后，j指向a（下标为3），即第k个字符的位置
可以看出来，模式串中，从开始第一个字符起的一段子串——长度为k-1的子串（ab），与以当前匹配字符的前一个字符为结尾的一段子串（ab），长度也是k-1，是有相等关系的，对于模式串，我们得出这样一个公式：
t(1)…t(k-1) = t(j-k+1)…t(j-1)
那么正是这长度为k-1的模式串的子串，决定了在遇到不匹配字符时，模式串指针重定位到第k个字符。 现在的问题就变成了： * 寻找模式串中下标为j的字符前的子串中长度为k-1的子串 * 使得存在t(1)…t(k-1) = t(j-k+1)…t(j-1)这样的关系
注意这两段可匹配的子串，必须要有这样几个条件： * 在下标为j的字符前。 * 第一段子串的开头元素必须是模式串的开头元素，第二段子串的结束元素必须是j-1为下标的元素。
看上去就是“掐头去尾”中的头和尾。
我们用到了next数组，next[j]=k表示在模式串中，第j个元素与主串中的元素失配后，模式串指针应当指向下标为k的模式串字符，重新和主串中相应字符比较。
栗子：
j模式串 a b a a b c a cnext[j]
到底怎么算next[j]呢？我昨晚上问了实验室的一个同学，他告诉我一方法：
规定，next[1] = 0。
在计算next[j]的时候，用手指挡住下标为j的字符，看之前的字符中有没有头尾相等的子串
如果有，那么这两个相等的子串就是我们找的长度为k-1的串。那么k=子串长度+1，这样就计算出来next[j]的值啦。
那么如果没有，说明k-1=0咯，那么k就是1。
此时，优化算法就成了：
int index(String S,String T,int pos){/*返回子串T在主串S中第pos位置字符后的位置，若不存在，返回值为0其中T非空，1<=pos<=S.length，S[0]和T[0]位置存储字符串长度*/i = pos;j = 1;while(i <= S[0] && j <= T[0]){if(S[i] == T[j]){i++;j++/*两个串的指针后退*/}else{j=next[j];}}if(j>T[0])return i-T[0];return 0}next数组到底怎么求
通过上面的讨论，可以知道，next数组和主串无关，只和模板串自身有关。按照教材上的说明，是由定义出发，通过递推的方式求得next函数值。
这里可以看做是模板串自己和自己进行比较。因为每寻找一个下标的next数值，都是在该下标之前的模式串的子串中寻找、比较看看里面有没有符合条件的两个长度为k-1的、相配的子串。
由定义知道 next[1] = 0
在和主串进行比较进行回退寻找k的时候，有这样的关系：
t(1)…t(k-1) = t(j-k+1)…t(j-1)
友谊之花、爱情之树、以及遗憾之泪！
