常见的字符串匹配时,模式串长度为n,源串长度为m,则从头匹配,两个指针i指向源串,j指向模式串,如遇到不同则回溯使j=0,这样就要重复匹配会使效率变低。
由于在现在i之前 的模式串与匹配串的匹配是相同的,即回溯时,不用将模式串与源串进行匹配,而只将模式串与自身匹配即可得到其是否需要回溯以及回溯到何处。则我们可以在进行模式匹配之前,想对模式串进行自我匹配,来计算出对于i在模式串的任意位置匹配失败后回溯的位置。
而对于自身匹配的算法还有一个优化的地方在于,模式串在b位置匹配到自身的a位置,然后判断一下这两个位置的字符是否相同,如果相同,则将a位置的回溯位置赋值给b,如果不同,则说明没有必要回溯到这个位置,因为回溯后不匹配,则直接将其置为0,表示从0开始重新匹配、
失败函数的返回值为-1是用来设置其结构,使其能够在自我匹配时简单实现其功能,标识匹配失败重新开始,但其在模式匹配中效果与0相同,都是i置为0,j++,然后继续匹配。
自我匹配放在一个失败函数中,对模式字符串进行操作,然后将结果放在一个数组中方便查询。
试着写出c++代码:
这里每次遍历时,是判断第i个字符串如果相同,那么第i加一个字符串不符就要返回的位置,每次都是对i+1进行操作,所以最后一次会对数组中下标为n的字符进行操作,会越界,则之前建fail数组时,要考虑一下。
void FailString(int f[],const char* str){
int length = strlen(str);
int i =0, k = -1;
f[0] = -1;
while( i < length){
if(k == -1 || str[i] == str[k]){
i++;k++;
if(str[i] == str[k])
f[i] = f[k];
else
f[i] = k;
}else
k = f[k];
}
}
bool compareString(const char* charA,const char* charB){
if( charA == 0 || charB == 0)
return false;
int Alen = strlen(charA);
int Blen = strlen(charB);
if( ! Alen || ! Blen )
return false;
if( Blen > Alen)return false;
int* fail = new int[ Blen+1 ];
FailString(fail,charB);
int i = 0 , j = 0;
while(i < Alen && j < Blen){
if( charA[i] != charB[j] ){
if(fail[i] == -1 )
j = 0;
else
j = fail[i];
}else
j ++;
i++;
}
delete[] fail;
fail =NULL ;
return j==Blen;
}
void main(){
char* s1 = "abcabcaabcabbac";
char* s2 = "abcabcabbac";
if(compareString(s1,s2))
cout<<"s1==s2"<<endl;
cin.get();
}
分享到:
相关推荐
《数据结构》串章节字符串的模式匹配KMP算法详解
《字符串模式匹配KMP算法》教学课例设计[归纳].pdf
模式匹配KMP算法C代码
字符串模式匹配KMP算法PPT学习教案.pptx
LZ77算法与模式匹配KMP算法的结合及算法实现.doc
KMP字符串模式匹配算法ppt,KMP算法是很精妙的算法,同时比较难懂。KMP字符串模式匹配算法ppt
模式匹配的kmp算法,可大大提高效率,时间复杂度仅为O(n*M),对于初学数据结构的有一定的帮助
kmp算法ppt,代码是pascal的,信息学奥赛的同学可以看看哦
模式匹配的KMP算法 模式匹配的KMP算法 模式匹配的KMP算法 模式匹配的KMP算法
《数据结构》用C语言实现的模式匹配KMP算法,可用于求出子串在主串中的位置。
这是个比较难理解的算法,虽然代码就那么几行,但真正理解清楚还是要会时间的。
严蔚敏版数据结构中的KMP算法的C++语言实现,有结果截图
KMP字符串模式匹配算法,内是ppt讲解,比较通俗易懂了。。
理解模式匹配的含义,掌握简单匹配算法及模式匹配KMP算法 思想,实现(1)编程动态实现简单模式匹配算法及模式匹配KMP算(2)根据给定的主串与模式串,给出根据两种匹配算法进行匹配的各趟匹配结果; 应用例子: ...
我以前一直理解不上去KMP算法(说心里话,我有点笨),当我看到这篇文章时,我理解了,这篇文章不错,说得挺细的,而且还免费,下了看看
字符串的模式匹配算法——KMP的C++实现。
这是重庆大学数据结构实验报告,题目是串的操作与KMP模式匹配算法。里面有完整的实验流程,包括源码及结果截屏
代码封装了字符串的kmp模式匹配算法。kmp是一种非常快速的字符串匹配算法,效率比普通匹配算法高很多
模式匹配中的KMP算法的c语言实现及简单的应用介绍!