题目链接：点击查看
题目大意：给出n组长度为60的字符串，问这n组中最长的公共连续子串是什么，若有多个不同的最长公共子串，输出字典序最小的那个
题目分析：一开始看到这个题目的时候我是没有想到暴力的。。加上昨天看了AC自动机的定义之后，一度怀疑这是不是个AC自动机的题目，所以就开启自暴自弃模式，正准备打开百度想借着这个题目去学学AC自动机来着，但打开一看发现这是个暴力+KMP的题目，暴力的话我们可以通过第一个字符串，枚举所有长度大于等于3的子串，其实自己算一下发现时间复杂度并不是很大，枚举的话大概是（60/3）+（60/4）+（60/5）……+（60/60）=20+15+12……+1，这么一算，我们直接放缩成20*60=1200，emmm，暴力枚举也只有1e3种情况，当然实际的话肯定连1e3都到不了，那么在枚举之后只需要判断后面的n-1个字符串中是否含有该子串即可，用KMP就能以至多（60*60）的时间复杂度判断每一个子串，那么总的时间复杂度也就是1e3*1e3*10，大概也才1e7多一丢丢，还算是比较小的，还有一个就是string类中find函数的实现好像就是KMP，然后我就偷懒没学KMP，直接用find函数过的这个题。。
不得不承认，cin加速外挂真的好用
代码：
#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std; typedef long long LL; const int inf=0x3f3f3f3f; const int N=1e6+100; int n; string s[15]; bool check(string target) { for(int i=2;i<=n;i++) if(s[i].find(target)==string::npos) return false; return true; } int main() { // freopen("input.txt","r",stdin); ios::sync_with_stdio(false); int w; cin>>w; while(w--) { cin>>n; for(int i=1;i<=n;i++) cin>>s[i]; bool flag=true; for(int len=60;len>=3;len--) { string ans; for(int i=0;i+len<=60;i++) { string temp=s[1].substr(i,len); if(check(temp)) if(ans.empty()||ans>temp) ans=temp; } if(ans.size()) { flag=false; cout<<ans<<endl; break; } } if(flag) cout<<"no significant commonalities"<<endl; } return 0; }
