BZOJ3277: 串(广义后缀自动机)
2018-06-29 06:14:35来源:博客园 阅读 ()
Submit: 1196 Solved: 478
[Submit][Status][Discuss]
Description
Input
Output
输出一行n个整数,第i个整数表示第i个字符串的答案。
Sample Input
abc
a
ab
Sample Output
HINT
Source
广义后缀自动机?就是把一坨字符串建到一个后缀自动机上??
不过好难理解啊qwq。。
对于这题,首先我们要知道几个定理
1.节点$i$表示的本质不同的字符串可以由$len[i] - len[fa[i]]$得到
2.一个串的子串 等价于 一个串所有前缀的所有后缀
这样子串就转换为求一个串的前缀的所有后缀的问题
前缀可以枚举,问题转换为求一个字符串的各个后缀在其他字符串中出现了多少次
这样我们可以把广义后缀自动机建出来,然后暴力沿着$parent$边跑,这样可以枚举出所有后缀
同时为了不重复枚举,我们需要记录下每个后缀是否已经被枚举过了
这样我们就可以知道一个状态出现的次数是否$>= K$,接下来我们只要统计出这个状态出现的次数就行了
根据定理$1$,这个很好统计
然后就做完啦
#include<cstdio> #include<iostream> #include<cstring> using namespace std; const int MAXN = 1e6 + 10; string s[MAXN]; int N, K; int fa[MAXN], len[MAXN], ch[MAXN][26], root = 1, last = 1, tot = 1, times[MAXN]; 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; len[nows] = len[pre] + 1; memcpy(ch[nows], ch[q], sizeof(ch[q])); fa[nows] = fa[q]; fa[q] = fa[now] = nows; for(; pre && ch[pre][x] == q; pre = fa[pre]) ch[pre][x] = nows; } } } int vis[MAXN], sum[MAXN]; void GetTimes() {//求出每一个状态在几个字符串出现过 for(int i = 1; i <= N; i++) { int now = root; for(int j = 0; j < s[i].length(); j++) { now = ch[now][s[i][j] - 'a'];//枚举每一个前缀 int t = now; while(t && vis[t] != i) vis[t] = i, times[t]++, t = fa[t];//枚举每一个后缀 } } } void dfs(int x) { if(x == root || vis[x]) return ; vis[x] = 1; dfs(fa[x]); sum[x] += sum[fa[x]]; } int main() { #ifdef WIN32 freopen("a.in", "r", stdin); #endif ios::sync_with_stdio(0); cin >> N >> K; for(int i = 1; i <= N; i++) cin >> s[i]; for(int i = 1; i <= N; i++) { last = 1; for(int j = 0; j < s[i].length(); j++) insert(s[i][j] - 'a'); } GetTimes(); for(int i = 1; i <= tot; i++) sum[i] = (times[i] >= K) * (len[i] - len[fa[i]]);//i状态所表示的子串集合对答案的贡献 memset(vis, 0, sizeof(vis)); for(int i = 1; i <= tot; i++) dfs(i); for(int i = 1; i <= N; i++) { int ans = 0, now = root; for(int j = 0; j < s[i].length(); j++) now = ch[now][s[i][j] - 'a'], ans += sum[now]; //枚举前缀,算出每一个前缀所包含的后缀对答案啊的贡献 printf("%d ", ans); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 【题解】洛谷 P1449 后缀表达式 2019-10-08
- P1349 广义斐波那契数列(矩阵乘法) 2019-08-16
- 中缀表达式转后缀表达式 2019-04-30
- LOJ#111. 后缀排序(二分 hash) 2018-08-02
- POJ1743 Musical Theme(后缀数组 二分) 2018-07-06
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