模式匹配(Pattern Matching) 即子串定位运算（Index函数）。
算法目的：确定主串中所含子串第一次出现的位置（定位） ——即如何实现 Index(S,T,pos)函数
初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(s)
操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符起第一次出现的位置；否则函数值为0。
注：S称为被匹配的串，T称为模式串。若S包含串T，则称“匹配成功”，否则称 “匹配不成功” 。
BF算法
BF算法设计思想：
将主串的第pos个字符和模式的第1个字符比较，若相等，继续逐个比较后续字符；
若不等，从主串的下一字符（pos+1）起，重新与第一个字符比较。
直到主串的一个连续子串字符序列与模式相等 。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。 否则，匹配失败，返回值 0 .
例如：
S=‘a b a b c a b c a c b a b’
T=‘a b c a c’ 返回pos=6
Int Index (SString S, SString T, int pos) {
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; } //指针回溯到 下一首位，重新开始匹配
} if(j>T[0]) //子串结束，说明匹配成功
return i-T[0]; //
匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。
else return0;
}//Index
若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下需要比较字符的总次数为
(n-m+1)*m＝O(n*m)
最恶劣情况是：主串中前面n-m+1个位置都部分匹配到子串的最后一位时出现不等，此时需要将指针i回溯，并从模式的第一个字符开始重新比较，每趟整个匹配过程中， while 循环执行m次，则总的while循环次数为(n-m+1)*m。
但一般情况下BF算法的时间复杂度为O(n+m)
KMP算法
求解next[j] 算法:
第一位的next值为0，第二位的next值为1，后面求解每一位的next值时，根据前一位进行比较。首先将前一位与其next值对应的内容进行比较，如果相等，则该位的next值就是前一位的next值加上1；如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。
详细解析：
当i=1时，j=0
当i=2时，j=1
当i=3时，看i的前一位即2的值为b，next值为1对应的内容是a，不相等，a的next值为0，所以j=1；
当i=4时，看i的前一位即3的值为a，next值为1对应的内容是a，相等 ，j=3的next值加1，所以j=2；
当i=5时，看i的前一位即4的值为a，next值为2对应的内容是b，不相等，再看2的next值1，对应的内容为a，与4相等，所以j=2的next值加1，所以j=2；
当i=6时，看i的前一位即5的值为b，next值为2对应的内容是b，相等，所以j=5的next值加1，为6
当i=7时，看i的前一位即6的值为c，next值为3对应的内容为a，不相等，3的next值为1对应的内容为a，不相等，所以j=1；
当i=8时，看i的前一位即7的值为a，next值为1对应的内容为a，所以j=7的next值加1，为2
next [ j ]是否完美无缺？
答：未必，例如当 S=‘a b a a a a b’,T=‘a a a a b’时,仍有多余动作
详细解析：
求nextval的值，是建立在求next值的基础上的。
当i=1时，nextval[1]的值为0；
当i=2时，2的值为a，2的next值为1对应的内容为a，相等，所以2的nextval[2]的值，继承nextval[1]的值为0；
当i=3时，3的值为a，3的next值为2对应的内容为a，相等，所以3的nextval[3]的值，继承nextval[2]的值为0；
当i=4时，4的值为a，4的next值为3对应的内容为a，相等，所以4的nextval[4]的值，继承nextval[3]的值为0；
当i=5时，5的值为b，5的next值为4对应的内容为a，不相等，所以5的nextval[5]的值，与其next值相等，为4
下面给出一个长的，加深印象。
123456789……
abcaabbabcabaacbacba
next: 01112231234532211211
nextval: 01102130110532210210
123456789……
abcaabbabcabaacbacba
next: 01112231234532211211
nextval: 01102130110532210210
KMP算法的时间复杂度
回顾BF的最恶劣情况：S与T之间存在大量的部分匹配，比较总次数为： (n-m+1)*m＝O(n*m)
而此时KMP的情况是：由于指针i无须回溯，比较次数仅为n,即使加上计算next[j]时所用的比较次数m，比较总次数也仅为n+m=O(n＋m)，大大快于BF算法。
注意：由于BF算法在一般情况下的时间复杂度也近似于O(n+m),所以至今仍被采用。
KMP算法的用途：
因为主串指针i不必回溯，所以从外存输入文件时可以做到边读入边查找，“流式”作业！