BZOJ2946 [Poi2000]公共串(后缀自动机)
程序员文章站
2023-11-11 16:52:34
Description 给出几个由小写字母构成的单词,求它们最长的公共子串的长度。任务:l 读入单词l 计算最长公共子串的长度l 输出结果 Input 文件的第一行是整数 n,1<=n<=5,表示单词的数量。接下来n行每行一个单词,只由小写字母组成,单词的长度至少为1,最大为2000。 Output ......
Description
给出几个由小写字母构成的单词,求它们最长的公共子串的长度。
任务:
l 读入单词
l 计算最长公共子串的长度
l 输出结果
Input
文件的第一行是整数 n,1<=n<=5,表示单词的数量。接下来n行每行一个单词,只由小写字母组成,单词的长度至少为1,最大为2000。
Output
仅一行,一个整数,最长公共子串的长度。
Sample Input
3
abcb
bca
acbc
Sample Output
2
其实这题我没A因为权限号密码忘了 但是在COGS过了那就发一下吧。。
感觉很zz啊,和单个串有什么区别。
那就直接把除了第一个串之外的SAM建出来然后枚举第一个串暴力匹配求最小就好了
1Ahhh
update:
??为什么网上的题解都和我不一样??
这题好像只建一个SAM就行了??!!感觉自己好菜啊。。。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN = 2001 * 2, INF = 1e9 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } struct SuffixAut { int fa[MAXN], len[MAXN], ch[MAXN][27], tot, last, root, ans, cur; SuffixAut() { cur = tot = last = root = 1; ans = 0;} void insert(int x) { int now = ++tot, pre = last; last = now; len[now] = len[pre] + 1; for(; pre && !ch[pre][x]; pre = fa[pre]) ch[pre][x] = now; if(!pre) fa[now] = root; else { int q = ch[pre][x]; if(len[q] == len[pre] + 1) fa[now] = q; else { int nows = ++tot; memcpy(ch[nows], ch[q], sizeof(ch[q])); fa[nows] = fa[q]; fa[q] = fa[now] = nows; len[nows] = len[pre] + 1; for(; pre && ch[pre][x] == q; pre = fa[pre]) ch[pre][x] = nows; } } } int work(int x) { if(ch[cur][x]) {cur = ch[cur][x]; ans++; return ans;} for(; cur && !ch[cur][x]; cur = fa[cur]); if(!cur) cur = root, ans = 0; else ans = len[cur] + 1, cur = ch[cur][x]; return ans; } }Suf[6]; char s[6][MAXN]; int N[6]; int main() { #ifdef WIN32 freopen("a.in", "r", stdin); #else freopen("pow.in", "r", stdin); freopen("pow.out", "w", stdout); #endif int num = read(); for(int i = 1; i <= num; i++) scanf("%s", s[i] + 1), N[i] = strlen(s[i] + 1); for(int i = 2; i <= num; i++) for(int j = 1; j <= N[i]; j++) Suf[i].insert(s[i][j] - 'a'); int out = 0; for(int i = 1; i <= N[1]; i++) { int ans = INF; for(int j = 2; j <= num; j++) ans = min(ans, Suf[j].work(s[1][i] - 'a')); out = max(out, ans); } printf("%d", out); return 0; }
下一篇: Floyd 算法详解