POJ 3080 Blue Jeans

知识点: 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() {
//find substr
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;
}


--------------------------END--------------------------
喜欢的话,不妨请我喝杯奶茶(≧∇≦)ノ