后缀数组,KMP扩展,自动机
题目要求4000个长度为200的字串的最长公共子串.
只需选一个串作为基串, 枚举它的所有后缀串S[i..len], 求出其它串与这个子串的LCP. 最后选最大的输出.
关于求串S与串T所有后缀的LCP, 林希德的论文讲了扩展KMP算法. 不过我想出另一种方法:
把S和T直接连接得到新串U. 按正常KMP的方法求U的next数组, 不过当p指向U[len[S]+1]即原T串的首字母时, 直接将此位的next置为0.
最后min(len[S], next[k]) 就是串T[1..(k-len[S])]与串S的lcp长度.
代码如下:
1
#include <iostream>
2using namespace std;
3
4char wd[4000][201];
5int cnt[201][201], vis[201][201];
6char ss[401];
7int next[401];
8int N;
9
10bool readin()
11
{
12
scanf("%d",&N);
13 if(N==0)return false;
14
15 for(int i=0; i<N; i++)
16 scanf("%s",wd[i]);
17 return true;
18
}
19
20int mycmp(char *s1, int l1, char *s2, int l2)
21{
22 if(l1!=l2) return (l2-l1);
23 while(--l1 && *s1==*s2) s1++, s2++;
24 return (*s1-*s2);
25}
26
27void mycpy(char *s1, char *s2, int l)
28{
29 while(l--) *(s1++)=*(s2++);
30 *s1=0;
31}
32
33void solve()
34{
35 memset(cnt,0,sizeof(cnt));
36 memset(vis,0,sizeof(vis));
37
38 int l0=strlen(wd[0]);
39 strcpy(ss,wd[0]);
40 char ans[201]="";
41
42
for(int p=0; p<l0; p++){
43 char *s=&ss[p];
44 for(int i=1; i<N; i++){
45 strcpy(&ss[l0], wd[i]); //连接两个串
46 int l1=l0-p+strlen(wd[i]);
47 next[0]=-1;
48 int p0=-1, p1=0;
49 while(p1<l1){
50 while(p0>=0 && s[p0]!=s[p1])
51 p0=next[p0];
52 next[++p1]=++p0;
53 if(p1==l0-p) //此位置0
54 next[p1]=0, p0=0;
55 if(p1>=l0-p){
56 int len=min(l0-p, next[p1]);
57 if(vis[p][p+len-1]!=i)
58 vis[p][p+len-1]=i, cnt[p][p+len-1]++;
59
}
60 }
61 }
62
63 for(int j=l0-1; j>=p; j--){
64 if(cnt[p][j]==N-1){
65 if(mycmp(&ss[p], j-p+1, ans, strlen(ans))<0)
66 mycpy(ans, &ss[p], j-p+1);
67 }
68 }
69 }
70
71 if(ans[0]==0)
72 puts("IDENTITY LOST");
73 else
74 puts(ans);
75}
76
77int main()
78{
79 while(readin()){
80 solve();
81 }
82}
83
posted on 2009-07-31 13:46
wolf5x 阅读(695)
评论(0) 编辑 收藏 引用 所属分类:
acm_icpc