首页 > 代码库 > BZOJ 4502: 串 AC自动机
BZOJ 4502: 串 AC自动机
4502: 串
Submit: 195 Solved: 95
[Submit][Status][Discuss]
Description
兔子们在玩字符串的游戏。首先，它们拿出了一个字符串集合S，然后它们定义一个字
符串为“好”的，当且仅当它可以被分成非空的两段，其中每一段都是字符串集合S中某个字符串的前缀。
比如对于字符串集合{"abc","bca"}，字符串"abb"，"abab"是“好”的（"abb"="ab"+"b",abab="ab"+"ab"），而字符串“bc”不是“好”的。
兔子们想知道，一共有多少不同的“好”的字符串。
Input
第一行一个整数n，表示字符串集合中字符串的个数
接下来每行一个字符串
Output
一个整数，表示有多少不同的“好”的字符串
Sample Input
2
ab
ac
ab
ac
Sample Output
9
HINT
1<=n<=10000，每个字符串非空且长度不超过30，均为小写字母组成。
Source
颂魔和毒爷把这道题加强了一下$\sum S \le 10^6$，然后给了一个更容易的做法。我偷一发题解.....
正解大概是讲：先钦定一个串C，只在最右边分割点统计。对于{S}中两前缀A,B。定义(A,B)合法仅当不存在划分B的一个前缀，接到A后面得到的(A‘,B‘)。那么就考虑一对(A,B)是否合法。
先枚举B，然后再统计多少A后面可以接B的前缀。这里是可以接，而不是接多少次，所以直接用最短的前缀其判断。
这个最短的另一个要求是B‘也存在{S}集中。所以可以等价于求一个最长的B‘。就是找一个最长的B的后缀，这个可以用fail树求出。
由B‘就定位B的最短前缀（Trie树定位），然后就统计它是{S}多少个A‘的后缀（用fail树统计）。
无声PPT
Code
#include< cstdio >#include< cstring >#define gec getchar#define FILE(F) freopen(F".in","r",stdin),freopen(F".out","w",stdout)#define DEBUG fprintf(stderr,"Passing [%s] in Line (%d)\n",__FUNCTION__,__LINE__)typedef long long ll;templateinline void read(T &x){ x=0;bool f=0;char c=gec(); for(;c<‘0‘||c>‘9‘;c=gec())f=(c==‘-‘); for(;c>=‘0‘&&c<=‘9‘;c=gec())x=x*10+c-‘0‘; x=f?-x:x;}const int MAXN(1000010);int Case,n,leng; char str[MAXN];ll Ans;namespace ACmaton{ struct ACtrie { int nx[26],fail,sum,Dep; }trie[MAXN];int ktot=1,root=1; void ins() { int k=1; for(int i=1;i<=leng;i++) { if(!trie[k].nx[str[i]-‘a‘])trie[k].nx[str[i]-‘a‘]=++ktot; trie[trie[k].nx[str[i]-‘a‘]].Dep=trie[k].Dep+1; k=trie[k].nx[str[i]-‘a‘]; } } int que[MAXN],l,h,now; void BFS() { for(int v=0;v<26;v++) if(trie[root].nx[v]) { trie[trie[root].nx[v]].fail=root; que[++l]=trie[root].nx[v]; }else trie[root].nx[v]=root; while(h<l) { now=que[++h]; for(int v=0;v<26;v++) if(trie[now].nx[v]) { trie[trie[now].nx[v]].fail=trie[trie[now].fail].nx[v]; que[++l]=trie[now].nx[v]; }else trie[now].nx[v]=trie[trie[now].fail].nx[v]; } } int p[MAXN],cnt[MAXN]; void Pretreat() { for(int i=1;i<=ktot;i++)cnt[trie[i].Dep]++; for(int i=1;i<=ktot;i++)cnt[i]+=cnt[i-1]; for(int i=ktot;i>=1;i--)p[cnt[trie[i].Dep]--]=i; for(int i=ktot;i>=1;i--) { trie[p[i]].sum++; trie[trie[p[i]].fail].sum+=trie[p[i]].sum; } trie[root].sum=1; } int st[MAXN],tp; void Dfs(int x) { st[++tp]=x; for(int v=0;v<26;v++) if(trie[trie[x].nx[v]].Dep==trie[x].Dep+1)Dfs(trie[x].nx[v]); int Pre=trie[x].Dep-trie[trie[x].fail].Dep; tp--;if(trie[x].fail!=root)Ans-=trie[st[Pre+1]].sum-1;//保留本身一个 } }using namespace ACmaton;int main(){ FILE("string"); read(Case); read(n); for(int i=1;i<=n;i++) { scanf("%s",str+1);leng=strlen(str+1); ins(); } Ans=((ll)ktot-1ll)*(ktot-1); BFS(); Pretreat(); Dfs(root); printf("%lld\n",Ans); return 0;}BZOJ 4502: 串 AC自动机
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。