字符串匹配之kmp算法

《字符串匹配之kmp算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一.简单的字符串匹配我们经常需要在某一串字符中查找是否存在给定的子串，我们将给定的子串叫做模式，查找子串的问题叫做模式匹配。进行字符串的模式匹配，最简单的方法就是依次将子串与给定的字符串依次进行比较。算法如下：intpatFind(constchar*str,constchar*pat){   intpos1,pos2;   boolisfind;   inti=0;   pos1=i;   pos2=0;   while(str[pos1]!=''&&pat[pos2]!=''){      if(str[pos1++]!=pat[pos2++]){         pos1=

2、++i;         pos2=0;      }   }   if(pat[pos2]==''){      returni;   }   return-1;} 简单的匹配算法存在回溯现象，复杂度为O(m*n)二.KMP算法的思想在匹配的时候经常会碰到回溯，而根据对Pattern的先验计算，能避免回溯，提高匹配效率，KMP算法就是通过对Pattern进行先验计算来避免回溯的算法。如p0...pi与ts...ts+i匹配，pi+1与ts+i+1不等，这时按照简单的匹配算法，将继续第s+1趟比较比较p0...pi-1...pm与ts+1...ts+i...ts+1+m,如果这两者匹

3、配，那么有p0...pi-1=ts+1...ts+i=p1...pi这时，如果已知两者不等，那么就不用做第s+1趟比较了。同理，如果已知p0...pi-2不等于p2...pi那么就不用做第s+2趟比较。依此类推，直到找到最大的k，使得p0...pk=pi-k...pi，这时可以直接做第s+i-k趟比较，并因为已知p0...pk=pi-k...pi=ts+i-k...ts+i了，直接比较pk+1和ts+i+1即可。 这时我们可以定义一个失效函数f(i)，比较至pi，使得pi匹配，pi+1不匹配时，其值等于使得p0...pk=pi-k...pi且小于i的最大k值，如果找不到则值为-1. ht

4、tp://mz.qqtop1.com对于模式pat=abaabcaba，f(0)为-1因为p0!=p1,f(1)为-1因为p0=p2,f(2)为0因为p0=p3,f(3)为0因为p0p1=p3p4,f(4)为1f(5)为-1f(6)为0f(7)为1f(8)为2 如果第s趟比较在第i位失配，则下一趟直接比较pf(i-1)+1和ts+i 三.失效函数的计算 已知f(j-1)=k,则有p0...pk=pj-1-k...pj-1,这时如果pk+1=pj,则f(j)=k+1,如果不等，则继续找f(k),因为p0...pf(k)=pj-1-f(k)...pj-1,这时如果pf(k)+1=pj,则f(

5、j)=f(k)+1,依此类推。我们可以得到下面的方法来计算失效函数。voidfailFunc(constchar*pat,int*fail){fail[0]=-1;intlen=strlen(pat);intk;for(intj=1;j=0&&pat[k+1]!=pat[j]){k=fail[k];}if(pat[k+1]==pat[j]){fail[j]=k+1;}else{fail[j]=-1;}cout<

6、ind(constchar*str,constchar*pat){intpos1=0,pos2=0;intpatlen=strlen(pat);int*fail=newint[patlen];failFunc(pat,fail);while(str[pos1]!=''&&pat[pos2]!=''){if(str[pos1]==pat[pos2]){pos1++;pos2++;}elseif(pos2==0){pos1++;}else{pos2=fail[pos2-1]+1;}}if(pat[pos2]==''){returnpos1-patlen;}return-1;}虽然

7、计算失效函数需要浪费一定的时间和空间，可是从代码我们可以看到KMP没有任何的回溯，时间复杂度仅为(m+n),当模式比较长时KMP算法比起简单的模式匹配有显著的优势。 运行结果：int_tmain(intargc,_TCHAR*argv[]){charstr[]="ababaabaabaabcabaaaabbcccc";charpat[]="abaabcaba";cout<