考研的专业课以及找工作的笔试题，对于串匹配模式都会有一定的考察，写这篇博客的目的在于进行知识的回顾与复习，方便遇见类似的题目不会纠结太多。
传统的BF算法
传统算法讲的是串与串依次一对一的比较，举例设目标串S=“ababcabcacb”,模式串T="abcac"，利用BF算法这个过程就会表示为：
将S串理解为数组，底标从0开始，即从a开始，第一次匹配过程如下：
ok，当发现T串尚未匹配结束，就开始出现了错误，S串坐标右移+1，开始从b匹配，过程如下：
出现不同，继续右移匹配，同理，直到最后匹配成功，如下：
成功之后，返回T串出现在S串的位置即可，其算法复杂度为O(mn)。由于ＢＦ算法代码简单，不再赘述。
改进之后的BF算法
改进的算法思想是先将T串的末尾最后一位与S串与之对应的位置进行比较，若发现不同，则后移下一位，若相同，再从T串的第一位开始比较,其算法复杂度为O(m+n)。
KMP算法：
对于串匹配问题，KMP算法最优。它改变了BF算法的回溯思路，并不是类似于BF算法一般一个一个的看，Instead，根据所求next数组的值进行移位。
KMP中next的求法：
对于上面所谈到的T串，其next＝{-1,0,0,0,1}
再者，比如abcaabbac,next={-1,0,0,0,1,1,2,0,2}
aabaaa,next={-1,0,1,0,1,4}
其实呢，不用考虑那么复杂，就是从尾到头和从头到尾比较，相同最长字符串的长度就是next值。
它之所以相对优化，是因为它的回溯要更省时间，当发现T[j]与S[i]不等时，就将T串右移j-next[j]个位置。
如此，便可以快速匹配。具体代码如下：
void GetNext(String T,int *next)
{
int i = , j;
next[]=-;
j=-;
while(i<T.length-)
{
if(j== - || T[i]==T[j])
{
i++;
j++;
next[i]==j;
}
else{
j=next[j];
}
}
}
KMP算法如下
int KMP(string S,string T,int *next)
{
int i=,j=;
while(i<S.length && j<T.length)
{
if(j == - || S[i] ==T[i])
{
i++;
j++;
}
else{
j=next[j];
}
}
if(j>T.length-)
return i-j+;
else
return -;
}
目前刷的面试题较少，后期继续跟进~
