串匹配模式中的BF算法和KMP算法

时间:2023-11-10 23:21:14

考研的专业课以及找工作的笔试题,对于串匹配模式都会有一定的考察,写这篇博客的目的在于进行知识的回顾与复习,方便遇见类似的题目不会纠结太多。

传统的BF算法

传统算法讲的是串与串依次一对一的比较,举例设目标串S=“ababcabcacb”,模式串T="abcac",利用BF算法这个过程就会表示为:

将S串理解为数组,底标从0开始,即从a开始,第一次匹配过程如下:

串匹配模式中的BF算法和KMP算法

ok,当发现T串尚未匹配结束,就开始出现了错误,S串坐标右移+1,开始从b匹配,过程如下:

串匹配模式中的BF算法和KMP算法

出现不同,继续右移匹配,同理,直到最后匹配成功,如下:

串匹配模式中的BF算法和KMP算法

成功之后,返回T串出现在S串的位置即可,其算法复杂度为O(mn)。由于BF算法代码简单,不再赘述。

改进之后的BF算法

改进的算法思想是先将T串的末尾最后一位与S串与之对应的位置进行比较,若发现不同,则后移下一位,若相同,再从T串的第一位开始比较,其算法复杂度为O(m+n)。

KMP算法:

对于串匹配问题,KMP算法最优。它改变了BF算法的回溯思路,并不是类似于BF算法一般一个一个的看,Instead,根据所求next数组的值进行移位。

KMP中next的求法:

串匹配模式中的BF算法和KMP算法

对于上面所谈到的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 -;
}

目前刷的面试题较少,后期继续跟进~