KMP又一小扩展 hdu1867
这个完全运用KMP模版，只不过用了两边而已，注意字典序，嗯，if判断那里着实有些...呃...代码如下：
#include <cstring>#include <stdio.h>#include <stdlib.h>#include <iostream>using namespace std;int next[100005];void build_next(string b){ int i,j=0,key=0; memset(next,0,sizeof(next)); for(i=1;i<b.size();i++) { j=next[i-1]; while(j==1 && b[i]!=b[j]) { j=next[j-1]; } if(b[j]==b[i]) { next[i]=j+1; } else next[i]=0; }}int KMP_Find(string s,string t) //pos从0开始,输出绝对位置要加1 {build_next(t);int i=0;int j=0;for(i=0;i<s.size();i++){while(j>0 && s[i]!=t[j]){j=next[j-1];}if(s[i]==t[j]){j++;}else{j=0;}}return j;}int main(){string s,t;while(cin>>s>>t){int a=s.size();int b=t.size();int x,y;x=KMP_Find(s,t);y=KMP_Find(t,s); if(x==y) { if(s>t) { cout<<t; for(int i=x;i<a;i++) cout<<s[i]; cout<<endl; } else { cout<<s; for(int i=x;i<b;i++) cout<<t[i]; cout<<endl; } } else if(x>y) { cout<<s; for(int i=x;i<b;i++) cout<<t[i]; cout<<endl; } else { cout<<t; for(int i=y;i<a;i++) cout<<s[i]; cout<<endl; }}return 0;}