KMP.rar_visual c

#include <iostream> #include <string> using namespace std; void findPreStr(char comp [],int move[]) { int strlen=0; while (comp[strlen]!='\0') { ++strlen; } int matchnum=0; move[1]=0; for (int index=2;index<strlen+1;++index) { while (matchnum>0&&comp[matchnum]!=comp[index-1]) { matchnum=move[matchnum]; } if (comp[index-1]==comp[matchnum]) { ++matchnum; } move[index]=matchnum; } } //数据结构书中的方法 待修正 void getNextVal(char *str,int move[]) { int len=strlen(str); int index=0; int matchnum=1; move[0]=0; move[1]=0; while (index<len) { if (matchnum==0||str[index]==str[matchnum]) { ++index; ++matchnum; if (str[index]!=str[matchnum]) { move[index]=matchnum; } else { move[index]=move[matchnum]; } } else { matchnum=move[matchnum]; } } } //下边求覆盖函数的算法是我自己的想法 void computePre(char * str,int move[]) { int length=strlen(str); move[0]=0; move[1]=0; for (int index=1;index<length;++index) { if (move[index]==0) { if (str[index]==str[0]) { move[index+1]=1; } else { move[index+1]=0; } } else { if (str[index]==str[move[index]]) { move[index+1]=move[index]+1; } else { move[index+1]=0; } } } } void matchfun(char * source,char * matchstr,int fun[]) { int length=strlen(source); if (length<strlen(matchstr)) { cout<<"fail find substr"<<endl; return; } int matchnum=0; int sumnumber=0; bool findflag=false; for (int index=0;index<length; ) { int curindex=index; while(source[curindex]==matchstr[matchnum]) { ++matchnum; ++curindex; //++sumnumber; } if (matchnum==strlen(matchstr)) { findflag=true; cout<<index<<":"<<matchstr<<endl; } if(matchnum) { index+=matchnum-fun[matchnum]; matchnum=0; } else { ++index; } ++sumnumber; } if (!findflag) { cout<<"fail find substr"<<endl; } cout<<length<<":"<<sumnumber<<endl; } void otherMatch(char * source,char * matchstr,int fun[]) { int len1=strlen(source); int len2=strlen(matchstr); if (len1<len2) { cout<<"match error"<<endl; return; } int matchnum=1; int index=0; while (matchnum<len2&&index<len1) { if (matchnum==0||source[index]==matchstr[matchnum]) { index++; matchnum++; } else { matchnum=fun[matchnum]; } } if (matchnum==len2) { cout<<"match success:"<<index-len2<<endl; } else { cout<<"match fail:"<<endl; } } //普通的匹配方法 void isInclude(char * source,char * com) { int len1=strlen(source); int len2=strlen(com); for (int i=0;i<len1;++i) { int index=i; for (int j=0;j<len2;++j) { if (source[index]!=com[j]) { break; } ++index; } if (j==len2) { cout<<"match success: "<<i<<endl; } } } void main() { char * source="kaacckkkkkkkkkkaaccddaabbmkkkkkkkkkkkkkk"; char* com="aacck"; int move[30]; isInclude(source,com); computePre(com,move); //findPreStr(com,move); //getNextVal(com,move); cout<<source<<endl; cout<<com<<endl; for (int i=1;i<strlen(com)+1;++i) { cout<<move[i]; } cout<<endl; matchfun(source,com,move); otherMatch(source,com,move); }