kmp.rar_KMP_visual c

#include <iostream> #include <string> using namespace std; void Next(string &Pattern,int *N) { //根据kmp算法得出的计算特征数组的函数，Pattern为模式串，N存储特征数组,本函数将处理Pattern含“？”的情况 int strlen=Pattern.size(); int i=1; N[0]=0; for(;i<strlen;i++) //循环求特征向量 { int k=N[i-1]; while(k>0&&Pattern[i]!=Pattern[k]) { if(Pattern[i]=='?'||Pattern[k]=='?') //当不匹配的字符是由于“？”引起的情况发生时 { N[i]=k+1; //特征值视为匹配 break; //匹配后进行下一位比较，退出本循环，break语句与下面的continue连用，避免了goto语句的出现 } else k=N[k-1]; } if((Pattern[i]=='?'||Pattern[k]=='?')&&(k!=0)&&Pattern[i]!=Pattern[k]) //由于“？”的关系，进行下一位比较 continue; if((Pattern[k]==Pattern[i])) //当前位匹配 N[i]=k+1; else { if(Pattern[0]=='?'||Pattern[i]=='?') //不匹配时若第一比较位为“？”特征值为1 N[i]=1; else //否则第一比较位特征值为0 N[i]=0; } } } void truncation(string & Pattern,string * str) { //将模式串以“*”为间隔前后分割，存入string型的数组中str，本函数处理含“*”的情况 int i=0,j=0,k=0; if(Pattern[i]=='*') //特殊情况的处理：第一个字符就是“*” { i=1; k=1; } int length=Pattern.size(); if(Pattern[length-1]!='*') //在串末尾加上一个“*”，则原有“*”前后的字串可以同等考虑（放入str中的字串为两个“*”之间或“*”与开头之间的部分） Pattern[length]+='*'; //这个方法是我和吕国成同学讨论的结果，在此对他表示感谢 while(Pattern[i]!='\0') { //循环截取子串 if(Pattern[i]!='*') //不是“*”则游标i后移 i++; else //遇到“*”后，从前一个“*”（或开头）后截取到这一个“*”前，存入str[j]中 { str[j]=Pattern.substr(k,i-k); k=++i; j++; } } } int KMP_FindPat(string &Target,string &Pattern,int startindex) { //利用改进的kmp算法进行模式匹配，Target为目标串，Pattern为模式串，startindex表示的是起始位置，如果成功就返回匹配位置，失败后返回-1 int len=Pattern.size(); int * N; N=new int[len]; //动态分布空间，用于存放特征值向量 Next(Pattern,N); //调用Next()函数 int h=-1; int LastIndex=Target.size()-Pattern.size(); if(LastIndex<=startindex) return h=-1; int i=startindex; int j=0; if(Pattern[startindex]=='?') //Pattern的第一个字符为“？”的处理情况 { i=startindex+1; j++; } for(;i<Target.size();i++) { while(Pattern[j]!=Target[i]&&j>0) { if(Pattern[j]=='?') { //由于“？”引起的字符不匹配被当作匹配，跳出while循环 j++; break; } j=N[j-1]; } if((Pattern[j]=='?')&&j!=Pattern.size()&&j!=0) continue; //这个语句的实现与Next函数中一样，与break一起避免了goto的出现 if(j==0&&Pattern[0]=='?') j++; if(Pattern[j]==Target[i]) j++; if(j==Pattern.size()) { return h=i-j+1; //匹配成功，返回匹配地址值 break; } } if(h==-1) return h; } void main() { cout << "***********************************************************************" << endl; cout << "***********************************************************************" << endl; cout << "************ Welcome to Use My Program!!! ************" << endl; cout << "************ Please follow the instructions ************" << endl; cout << "***********************************************************************" << endl; cout << "***********************************************************************" << endl; string Pattern; string Target; cout << "请输入目标串: "; cin >> Target; cout << "请输入匹配串: "; cin >> Pattern; int j,k; string * str; str=new string[128]; truncation(Pattern,str); //截取字串放入str中 int tag = 1; //若匹配成功为1，失败为0 for(int i=0;str[i]!="\0";i++) { int h=KMP_FindPat(Target,str[i],k=0); if(Target==Pattern) //处理特殊情况：Pattern与Target相等，匹配位为0 h=0; j=h; if(h==-1) //h为-1，则说明匹配失败 { tag = 0; cout << endl << "Bad Luck!!!" << endl; cout<<"Pattern Failed!!!"<<endl; cout << "Please tre again later." << endl << endl; break; } k+=str[k].size(); //比较被截取的下一段字串，开始位置为k之后的str[k].size处 } if(tag==1) { j=KMP_FindPat(Target,str[0],k=0); //j为被截取的第一位字串的起始匹配位，即为整个Pattern的起始匹配位 cout << endl << "Well Down!!!" << endl; cout<<"Pattern Succeeded"<<endl; cout<<"The first paterned position is "<< j <<endl; } } //我保证没有抄袭他人程序!!!