上周算法班的BEN老师花了1个小时讲自动机和KMP的关系,结果failed...明天又要上课了,花了半天时间看了下KMP,暂且停留在利用next求模式中的跳跃长度,自动机那个还不能理解。。。 具体的可以百度阮一峰的KMP算法。 看着什么前缀后缀,突然想到上下文无关文法乔姆斯基范式了。。。。又想到了NFA和正则表达式的转换,是时候复习复习了。。 太晚了,直接上代码,明天继续看ML和统计学!加油! [url=][/url]
1 #include <iostream> 2 #include <string> 3 #include <iterator>//输出 4 5 using namespace std; 6 void Next(string str, int next[]){ //自己跟自己匹配 7 int length=str.size(); 8 next[0]=-1; 9 int j=-1;10 for(int i=1;i<length;i++){11 while(j>-1 && str[j+1]!=str) j=next[j];12 if(str[j+1]==str) j++;13 next=j;14 }15 }16 void Match(string str1,string str2,int next[]){17 Next(str2,next);18 int length1=str1.size(),length2=str2.size();19 int j=-1;20 for(int i=0;i<length1;i++){21 while(j>-1 && str2[j+1]!=str1) j=next[j];22 if(str2[j+1]==str1) j++;23 if(j==length2-1){24 cout<<"Pattern occurs with shift "<<i-length2+1<<endl;25 j=next[j];26 }27 }28 }29 int main(){30 string str1="bbcabcdababcdabcdabde";31 string str2="abcdabd";32 int next[20];33 Match(str1,str2,next);34 copy(next,next+10,ostream_iterator<int>(cout," "));35 cout<<endl;36 return 0;37 }[url=][/url]
输出结果 MacBook-Pro:Algorithm root# g++ kmpdemo2.cpp -o kmpdemo2 MacBook-Pro:Algorithm root# ./kmpdemo2 Pattern occurs with shift 13 -1 -1 -1 -1 0 1 -1 0 0 0
|