首页 > 代码库 > 【BZOJ2946】公共串 [SAM]
【BZOJ2946】公共串 [SAM]
公共串
Time Limit: 3 Sec Memory Limit: 128 MB[Submit][Status][Discuss]
Description
给出几个由小写字母构成的单词，求它们最长的公共子串的长度。
任务：
l 读入单词
l 计算最长公共子串的长度
l 输出结果
Input
文件的第一行是整数 n ，表示单词的数量。接下来n行每行一个单词，只由小写字母组成，单词的长度至少为1，最大为2000。
Output
仅一行，一个整数，最长公共子串的长度。
Sample Input
3
abcb
bca
abcb
bca
acbc
Sample Output
２
HINT
2 <= n <= 5
Solution
因为要求所有串的最长公共子串，所以我们运用SAM，先对第一个串（基本串）构建一个SAM，然后用后面的串匹配即可。
记录 L[i] 表示当前串和基本串在 i 这个状态匹配的最长长度。显然，一个状态对答案的贡献是所有串和基本串匹配时 L[i] 的最小值。
然后取一个最大值即可。
Code
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 using namespace std; 9 10 const int ONE=4005; 11 const int INF=2147483640; 12 13 int T,n; 14 char str[ONE]; 15 int ans[ONE], q[ONE], L[ONE]; 16 int len[ONE], a[ONE][27], fa[ONE], v[ONE]; 17 int last, cnt; 18 int Ans; 19 20 int get() 21 { 22 int res=1,Q=1;char c; 23 while( (c=getchar())<48 || c>57 ) 24 if(c==‘-‘)Q=-1; 25 res=c-48; 26 while( (c=getchar())>=48 && c<=57 ) 27 res=res*10+c-48; 28 return res*Q; 29 } 30 31 struct SAM 32 { 33 SAM() {last = cnt = 1;} 34 void Add(int c) 35 { 36 int x = last, New = last = ++cnt; 37 len[New] = len[x] + 1; v[New] = 1; 38 while(x && !a[x][c]) a[x][c] = New, x = fa[x]; 39 if(!x) {fa[New] = 1; return;} 40 41 int q = a[x][c]; 42 if(len[x] + 1 == len[q]) fa[New] = q; 43 else 44 { 45 int Nq = ++cnt; len[Nq] = len[x] + 1; 46 memcpy(a[Nq], a[q], sizeof(a[q])); 47 fa[Nq] = fa[q]; 48 fa[New] = fa[q] = Nq; 49 while(a[x][c] == q) a[x][c] = Nq, x = fa[x]; 50 } 51 } 52 53 void Pre() 54 { 55 for(int i=1; i<=cnt; i++) v[len[i]]++; 56 for(int i=1; i<=cnt; i++) ans[i] = len[i]; 57 for(int i=1; i<=n; i++) v[i] += v[i-1]; 58 for(int i=cnt; i>=1; i--) q[v[len[i]]--] = i; 59 } 60 }; 61 SAM S; 62 63 void Check() 64 { 65 memset(L, 0, sizeof(L)); 66 n = strlen(str+1); 67 int x = 1, record = 0; 68 for(int i=1; i<=n; i++) 69 { 70 int c = str[i]-‘a‘+1; 71 while(x && !a[x][c]) x = fa[x]; 72 if(!x) {x = 1; record = 0; continue;} 73 record = min(record, len[x]) + 1; 74 x = a[x][c]; 75 L[x] = max(L[x], record); 76 } 77 78 for(int i=cnt; i>=1; i--) 79 L[fa[q[i]]] = max(L[fa[q[i]]], L[q[i]]); 80 for(int i=1; i<=cnt; i++) 81 ans[i] = min(ans[i], L[i]); 82 } 83 84 int main() 85 { 86 T = get(); T --; 87 scanf("%s", str+1); n = strlen(str+1); 88 for(int i=1; i<=n; i++) S.Add(str[i]-‘a‘+1); 89 S.Pre(); 90 91 while(T--) 92 { 93 scanf("%s", str+1); 94 Check(); 95 } 96 97 for(int i=1; i<=cnt; i++) 98 Ans = max(Ans, ans[i]); 99 100 printf("%d",Ans);101 }
【BZOJ2946】公共串 [SAM]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。