BZOJ2946 [Poi2000]公共串(后缀自动机)
2018-06-29 06:14:34来源:博客园 阅读 ()
Description
Input
Output
Sample Input
abcb
bca
acbc
Sample Output
HINT
Source
其实这题我没A因为权限号密码忘了 但是在COGS过了那就发一下吧。。 已AC
感觉很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; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 树结构基础 2020-02-18
- 浅谈LCA 2019-12-25
- C++动态规划实现查找最长公共子序列 2019-10-31
- 【CSP-S膜你考】最近公共祖先 To Be Continued 2019-10-12
- LCA最近公共祖先-- HDU 2586 2019-05-08
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash