知识点: KMP+枚举
题目链接 | Here
题意
最长公共子串问题,子串必须连续。
问: 最长的公共子串是什么?
每个字符串固定由60个字符组成,且最多有10个字符串。
输入
先输入$t$表示有$t$组案例。
每组案例先输入一个$n$,表示有$n$个字符串
之后输入$n$行字符串,每个字符串的字符个数为60
1 2 3 4 5 6 7 8 9 10 11 12
| 3 2 GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA 3 GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA GATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA GATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA 3 CATCATCATCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC ACATCATCATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AACATCATCATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
|
输出
- 若不存在输出no significant commonalities
- 否则输出字典序最小的最长子串
1 2 3
| no significant commonalities AGATAC CATCATCAT
|
题解
无脑暴力肯定会TLE,所以使用KMP加速在后续找匹配的速度。
因此只要在第一行中暴力找出所有可能的情况$\binom{2}{60}$,并使用KMP算法在接下来的几行中暴力匹配即可。
KMP复杂度太优秀了只要O(n+m)!!!
AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
| #include <cstdio> #include <string> #include <iostream> using namespace std;
int nxt[70]; int n,m; string p; string t[12];
void getNxt(int l) { int i=0,j=-1; nxt[0]=-1; while(i<l) { if(j==-1||p[i]==p[j]) { i++,j++; nxt[i]=(p[i]==p[j])? nxt[j] : j; } else { j=nxt[j]; } } }
bool kmp(int k,int l) { int i=0,j=0; while(i<60&&j<l) { if(j==-1 || t[k][i]==p[j]) i++,j++; else j=nxt[j]; } if(j==l) return 1; return 0; }
bool check(int l) { getNxt(l); for(int i=1; i<n; i++) { if(!kmp(i,l)) return 0; } return 1; }
void slove() { int len; string ans=""; bool flg=0; for(int i=0; i<60; i++) { len=60-i; for(int j=3; j<=len; j++) { p = t[0].substr(i,j); if(check(j)) { flg=1; ans = (p.size()>ans.size() || (p.size()==ans.size()&&p<ans))? p : ans; } } } if(flg) cout << ans << endl; else cout << "no significant commonalities\n"; }
int main() { std::ios::sync_with_stdio(false); cin >> m; while(m--) { cin >> n; for(int i=0; i<n; i++) cin >> t[i]; slove(); } return 0; }
|