知识点： 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;
}
|
