首页 > 代码库 > 字符串匹配算法——KMP算法
字符串匹配算法——KMP算法
处理字符串的过程中,难免会遇到字符匹配的问题。常用的字符匹配方法
1. 朴素模式匹配算法(Brute-Force算法)
求子串位置的定位函数Index( S, T, pos).
从目标串s=“s1s2…sn"的第一个字符开始和模式串t=“t1t2…tm"中的第一个字符比较,若相等,则继续逐个比较后续字符;
否则从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较。
依次类推,若从模式串s的第i个字符开始,每个字符依次和目标串t中的对应字符相等,则匹配成功,该算法返回i;否则,匹配失败,函数返回0。
2. 模式匹配的改进算法-KMP算法
KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的,简称KMP算法。该算法较BF算法有较大改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。
每趟匹配过程中出现字符比较不等时,不回溯主指针i,利用已得到的“部分匹配”结果将模式向右滑动尽可能远的一段距离,继续进行比较。
定义next[j]函数,表明当模式中第j个字符与主串中相应字符“失配”时,在模式中需重新和主串中该字符进行比较的字符的位置。(具体描述参见数据结构(严蔚敏版))
next函数的定义:
下面给出实现:
其中获取next数组的函数,和课本描述稍微有点差异。原文使用字符串第一个值表示字符串的大小,真正的字符串内容从第二个字符开始,和平时使用不一致,本文将其改变。并对next数组的值的意义进行改变,认为next值为-1时,匹配失效,需要改变主串的比较的数组(i+1),即相对于课本,把所有next值减一,而意义不变。
1 #include <cstdio> 2 #include <string> 3 using namespace std; 4 5 void get_next(string p, int* next) 6 { 7 int sp = p.size(); 8 next[0]=-1; 9 10 int i,j;11 i=0;j=-1;12 13 while(i<sp-1)14 {15 if(j==-1||p[i]==p[j])16 {17 ++i;++j;18 if(p[i]!=p[j])19 next[i]=j;20 else21 next[i]= next[j];22 }23 else24 {25 j=next[j];26 }27 }28 }29 void printNext(int* next,int n)30 {31 for(int i =0; i<n;i++)32 printf("%d ",next[i]);33 printf("\n");34 }35 int kmp_search(string s, string pattern,int pos)36 {37 int sizeP = pattern.size();38 int sizeS = s.size();39 40 int *next = new int[sizeP];41 memset(next,0,sizeof(int)*sizeP);42 43 get_next(pattern,next);44 printNext(next,sizeP);45 46 int i,j;47 i=0;j=0;48 49 while(i<sizeS&&j<sizeP)50 {51 if(j==-1||s[i]==pattern[j])52 {53 ++i;++j;54 }55 else56 {57 j=next[j];58 }59 }60 61 delete next;62 63 if(j==sizeP)64 {65 return i-sizeP;66 }67 else 68 return -1;69 70 }71 int main()72 {73 string s = "abacaesabacadfabacawersdf";74 string pat = "abacaw";75 int result = kmp_search(s,pat,0);76 printf("s: %s\tt: %s\npos: %d\n",s.c_str(),pat.c_str(),result);77 return 0;78 }