1.暴力匹配算法
2.KMP
KMP算法描述见算法导论
//字符串匹配算法 #include <iostream> using namespace std; //暴力匹配方法 bool ismatch(char *a,char *b) { int alen=strlen(a); int blen=strlen(b); int i=0; int j=0; while(i<alen&&j<blen) { if (a[i]==b[j]) { ++i; ++j; } else { i=i-j+1; j=0; } } if (j==blen-1) { return true; } else { return false; } } void GetNext(char* p,char *&next) { int len=strlen(p); int k=-1; int j=0; next[0]=-1; while (j<len-1) { if (k==-1||p[j]==p[k]) { ++k; ++j; next[j]=k; } else { k=next[k]; } } } //KMP算法 bool KMPmatch(char *a,char *b,char *next) { int alen=strlen(a); int blen=strlen(b); int i=0; int j=-1; while(i<alen&&j<blen) { if (j==-1||a[i]==b[j]) { ++i; ++j; } else { j=next[j]; } } if (j==blen-1) { return true; } else { return false; } } int main() { char *a="BBC ABCDAB ABCDABCDABDE"; char *b="ABCDABD"; bool canmatch=false; canmatch=ismatch(a,b); if (canmatch==true) { cout<<"match"<<endl; } else { cout<<"no match"<<endl; } const int num=strlen(b); char *next=new char[num]; GetNext(b,next); canmatch=KMPmatch(a,b,next); if (canmatch==true) { cout<<"match"<<endl; } else { cout<<"no match"<<endl; } return 0; }