题意:和 POJ-3080 Blue Jeans 基本上一样:求n个串的公共子串,只是数据增大了(字符串长度)
完整代码:
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cmath> using namespace std; const int Naxn = 300; const int maxn = 4e3+5; int nex[Naxn]; string s[maxn]; void getnext(string s2,int len){ int i=0,j=-1; nex[i] = j; while(i<len){ if(j==-1||s2[i]==s2[j]) nex[++i] = ++j; else j = nex[j]; } } int kmp(string s1,int len1,string s2,int len2){ int i=0,j=0; while(i<len1){ if(j==-1||s1[i]==s2[j]){ i++; j++; }else j = nex[j]; if(j==len2) return 1; } return 0; } int main(){ ios::sync_with_stdio(0); cin.tie(0); int n,m; while(cin>>n){ if(!n) break; for(int i=0;i<n;i++){ cin>>s[i]; } string ans = ""; for(int i=0;i<s[0].size();i++) for(int j=1;j+i<=s[0].size();j++){ string res; bool flag = false; res = s[0].substr(i,j); getnext(res,res.size()); for(int k = 1;k<n;k++){ if(!kmp(s[k],s[k].size(),res,res.size())){ flag = true; break; } } if(!flag){ if(ans.size()<res.size()) ans = res; else if(ans.size() == res.size()) ans = min(ans,res);//最小字典序 } } if(ans.size()) cout<<ans<<endl; else cout<<"IDENTITY LOST"<<endl; } return 0; }