題目鏈接：點擊查看

題目大意：給出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; }

總結

以上是生活随笔為你收集整理的POJ - 3080 Blue Jeans(暴力+KMP)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。