《数据结构（C语言版）》上给出了两种模式匹配算法，BF算法和KMP算法。
存在一个主串S和一个模式T，要在主串S中查找与模式T相匹配的子串。
BF算法
操作步骤：
分别利用计数指针
i和j指示主串和模式T中当前正待比较的字符位置，i初值为pos，j初值为1；如果两个串均未比较到串 尾，即i 和j 均分别小于等于S和T的长度时，则循环执行以下操作：
·S.ch[i]和T.ch[j]比较，若相等，则i和j分别指向串中的下个位置，继续比较后续字符；
· 若不等，指针后退重新开始匹配，从主串的下一个字符(i = i - j+2）起再重新和模式的第一个字符（j = 1）比较；如果
j >T.length,说明匹配成功，返回和模式T中第一个字符相等的字符在主串S中的序号(i - T.length）；否则不成功，返回 0。
int index_BF(SqString s,SqString t，int pos)
{
i = pos;j=1;
while (i<s.length && j<t.length)
{
if (s.ch[i]==t.ch[j])
{
i++; //依次匹配下一个字符
j++;
}
else //回溯重新开始下一次匹配
{
i=i-j+2; //主串从下一个位置开始匹配
j=1; //子串从头开始匹配
}
}
if (j>=t.length)
return(i-t.length); //匹配成功
else return 0; //模式匹配不成功
}
重要的在于理解BF如何变为更高大上的KMP
BF算法在运行时：如果模式与主串已经部分匹配，但最后一个出现了不匹配，那么按照BF算法，i回退到 i-j+2，j 回退到 1， 这样的话仅仅因为最后一个字符的不匹配便要抛弃一切再次开始(⊙﹏⊙)。
不过如果在多次的匹配过程中，有一次匹配出现了部分匹配，那么按照BF算法就要回退，继续，然后不匹配，不匹配···，直到有一次又出现了部分匹配，这个不断比较，后退，比较、后退的过程实在太那个什么了。
但仔细一想，之前有一次部分匹配了（也就是说在主串中有一段子串和模式的前面部分完全相同），然后按BF算法来说，要回退再重新开始比较，但这样继续下去（不断比较），其实不就是主串中一个与模式相同的子串进行比较吗（严谨来说回退后少了几个，不过如果部分匹配的部分较长的话，也是存在很多相同的）？ 那不就是等同于自己与自己比较了吗。
假设主串中那个与模式部分匹配的子串为s1，那么T中的为t1，在s1的部分与t1进行比较时，如果又出现了部分匹配(s1 的子串 s1'和 t1 的子串t1'），那么要是能早知道在s1的后面有与t1前面相同的小子串，那就不用回退那么多了，就直接回退到s1后面与t1'相同的部分不就省了很多步骤吗（也省了很多时间）。
既然如此，不如先把自己比较一遍，把结果存下来(next[]数组），下次又出现部分匹配的情况，就根据自己存下来的数据（本身的特点）合理的回退，这样就减少了冗余（本质或者说精髓是对模式进行预处理）。
KMP算法
next[]求解的自然语言定义：
j=1; next[1]=0;
模式中第 j 个字符之前，前后（首尾）相等的最长真子串长度加一;
其他next[j] = 1;
计算 next 函数值
void get_next(SString T,int next[])
{
i=1;next[1]=0;j=0;
while(i <T.length)
{
if(j==0||T.ch[i] == T.ch[j] ) { ++i; ++j; next[i] = j; }
else j = next[j];
}
}
例：‘
模式串 a b a b c d a b c a
next [ ] 0 1 1 2 3 1 1 2 3 1
nextval 0 1 0 1 3 1 0 1 3 0
next[ ]值：
- 第一个 a next[j] = 0 ,下一个；
- b 之前只有一个 a ，next[j] = 1，下一个；
- a 之前没有相等的字符， next[j] = 1；
- b 之前的 a 与模式的首部 a 相同，相同字符数为 1 ，那么next[j] 为首尾相等的最长真子串长度加一 ，为 2；
- c 之前的 ab 与首部的 ab 相同，同理 ，next[j] = 2+1 = 3;
- d 之前没有首尾相等的真子串，为 1；
...
nextval[ ]值 :
算法：
· 第一位为 0；
· 从第二位开始，模式的字符要和其 next[] 的值（这个值要比自己的位置号小）所对应的字符相比，如果相等，第 i 位的 nextval[ i ] = nextval[ next[ i ] ]，如果不等，把其next值照抄下来即可；
nextval[ 1 ] =0；
在第二位开始， nextval [ i ] 等于将该位的字符与该位的next[] 的值所指向的字符比较，即 第二位为 b ，其next[] 数据为 1 ,则将 b 与 模式的第 1 个 ( a ) 比较 ， b 不等于 a ，那么nextval[] 等于 next[] 值，如果相等则 nextval [ i ] = naxtval[ naxt[ i ] ] ；
a ，next[ i ]值为 1 ，和模式第一个比较，相同，nextval[ i ] = nextval[ next[ i ] ] = 0；
b， next[ i ]值为 2 ，和第二个比较，相等 ，nextval[i] = nextval[ next[i] ] = nextval[ 2 ] = 1；
...
验证 ：
串 " ababaabab " 的 nextval 为 010104101.
