poj 3080 Blue Jeans (n个字符串的最长公共子串，暴力+kmp)
题意：给出n个字符串（n<=10），字符串长度不超过70，问出现在全部n个字符串中的最长并且字典序最小的长度大于等于3的子串。
思路：数据范围很小。。。直接暴力枚举+kmp匹配一下。。。
/* ***********************************************
Author :111qqz
Created Time :2016年08月11日 星期四 01时29分02秒
File Name :code/poj/3080.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <stack>
8#include <set>
9#include <map>
10#include <string>
11#include <cmath>
12#include <cstdlib>
13#include <deque>
14#include <ctime>
15#define fst first
16#define sec second
17#define lson l,m,rt<<1
18#define rson m+1,r,rt<<1|1
19#define ms(a,x) memset(a,x,sizeof(a))
20typedef long long LL;
21#define pi pair < int ,int >
22#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=70;
7int nxt[N];
8string dna[15];
9int n ;
10void getnxt( string a)
11{
12 int i = 0 ;
13 int j = -1;
14 int n = a.length();
15 nxt[0] = -1;
16 while (i<n)
17 if (j==-1||a[i]==a[j]) nxt[++i]=++j;
18 else j = nxt[j];
19}
20bool kmp(string a,string b)
21{
22 int m = a.length();
23 int n = b.length();
24 getnxt(a);
25 int i = 0;
26 int j = 0;
27 while (i<n)
28 {
29 if (j==-1||a[j]==b[i]) i++,j++;
30 else j=nxt[j];
31 if (j==m) return true;
32 }
33 return false;
34}
35int main()
36{
37 #ifndef ONLINE_JUDGE
38 freopen("code/in.txt","r",stdin);
39 #endif
40 int T;
41 ios::sync_with_stdio(false);
42 cin>>T;
43 while (T--)
44 {
45 cin>>n;
46 for ( int i = 1 ; i <= n ; i++) cin>>dna[i];
47 string ans="";
48 int len = dna[1].length();
49 //cout<<"len:"<<len<<endl;
50 for ( int i = 0 ; i < len ; i++)
51 for ( int j = 1 ; i+j-1 < len ;j++)
52 {
53 bool match = true;
54 string tmp = dna[1].substr(i,j);
55 // cout<<"tmp:"<<tmp<<endl;
1 for ( int k = 2 ; k <= n; k++)
2 if (!kmp(tmp,dna[k]))
3 {
4 match = false;
5 break;
6 }
7 if (match)
8 {
9 // cout<<"ccc"<<endl;
10 if (tmp.length()>ans.length())
11 ans = tmp;
12 else if (tmp.length()==ans.length()&&tmp<ans)
13 ans = tmp;
14 }
15 }
16 if (ans.length()<3)
17 cout<<"no significant commonalities"<<endl;
18 else
19 cout<<ans<<endl;
}
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}