BZOJ4502: 串(字符串，AC自动机）

前言：BZOJ P4502 串 题面：输入格式：输出格式：样例输入：样例输出：数据范围： 分析： 然后开始码代码：全代码：

前言：

完全不会AC自动机，老早想学，今天写题目遇到，就来写一发题解。然后，人生第一道AC自动机就是省选题，我也很无奈啊。

BZOJ P4502 串

题面：

兔子们在玩字符串的游戏。首先，它们拿出了一个字符串集合 S，然后它们定义一个字符串为“好”的，当且仅当它可以被分成非空的两段，其中每一段都是字符串集合 S 中某个字符串的前缀。比如对于字符串集合{“ abc a b c ”, “ bca b c a ”}，字符串” abb a b b ”，” abab a b a b ”是“好”的（” abb a b b ” = “ ab a b ”+” b b ”, abababab = “ ab a b ” + “ ab a b ”），而字符串“ bc b c ”不是“好”的。 兔子们想知道，一共有多少不同的“好”的字符串。

输入格式：

第一行一个整数 n，表示字符串集合中字符串的个数 接下来每行一个字符串

输出格式：

一个整数，表示有多少不同的“好”的字符串

样例输入：

2 ab ac

样例输出：

9

数据范围：

对于 20%的数据，1 <= n <= 200 对于 50%的数据，1 <= n <= 2000 对于 100%的数据，1 <= n <= 10000，每个字符串非空且长度不超过 30，均为小写字母组成。

分析：

首先看题，知道这是一道字符串操作题，然后弃寮。

再然后，补题。 因为我们要找两个前缀拼在一起组成一个新的串，所以我们用补集转换，先将 ans a n s 赋成节点树的平方再从中减去重复的。 emmmmmmmm。。。。。。。。这看上去不简单。

然后开始码代码：

定义一些变量：

int n,xia[N][26],tot; int dep[N],ans,num[N];//dep记录节点的深度，ans表示答案。 int pre[N],cnt[N],tuo[N]; int top,sui[N]; queue<int> q; char s[N];

先建一棵 trie t r i e 树。

read(n); tot=1;//一定要把tot赋成1，我调了好久。 for(int cas=1;cas<=n;cas++) { scanf("%s",s); int len=strlen(s); for(int i=0,flag=1;i<len;i++)//建立trie树。 { int c=s[i]-'a'; if(!xia[flag][c]) xia[flag][c]=++tot; dep[xia[flag][c]]=dep[flag]+1; flag=xia[flag][c]; } }

然后用 fail f a i l 指针构建一棵新的树，这棵树有很多好的性质，比如所有的父亲都是他的一个前缀。

for(int i=0;i<26;++i)//建立trie树上的fail指针。 if(xia[1][i]) { pre[xia[1][i]]=1; q.push(xia[1][i]); } else xia[1][i]=1; for(;!q.empty();)//以fail指针建一棵树，便于下面查找。 { // writeln(66); int flag=q.front(); q.pop(); for(int i=0;i<26;i++) if(xia[flag][i]) { pre[xia[flag][i]]=xia[pre[flag]][i]; q.push(xia[flag][i]); } else xia[flag][i]=xia[pre[flag]][i]; }

利用拓扑排序，将这棵树的节点拓扑一边。

for(int i=1;i<=tot;i++) cnt[dep[i]]++; for(int i=1;i<=tot;i++) cnt[i]+=cnt[i-1]; for(int i=tot;i;--i) tuo[cnt[dep[i]]--]=i; for(int i=tot;i;--i) { int zz=tuo[i]; ++num[zz]; num[pre[zz]]+=num[zz]; }num[1]=1;

然后dfs一边，稍微带点小容斥，更新 ans a n s ，最后输出。

全代码：

#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<time.h> #include<vector> #include<cstring> #include<stdlib.h> #include<iostream> #include<algorithm> #define LL long long using namespace std; const LL N=3e5+10; const LL mod1=1000+7; const LL inf=0x3f3f3f3f; const LL mod2=233333333; namespace FastIO { template<typename tp> inline void read(tp &x) { x=0; register char c=getchar(); register bool f=0; for(;c<'0'||c>'9';f|=(c=='-'),c = getchar()); for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar()); if(f) x=-x; } template<typename tp> inline void write(tp x) { if (x==0) return (void) (putchar('0')); if (x<0) putchar('-'),x=-x; LL pr[20]; register LL cnt=0; for (;x;x/=10) pr[++cnt]=x%10; while (cnt) putchar(pr[cnt--]+'0'); } template<typename tp> inline void writeln(tp x) { write(x); putchar('\n'); } } using namespace FastIO; int n,xia[N][26],tot; int dep[N],ans,num[N];//dep记录节点的深度，ans表示答案。 int pre[N],cnt[N],tuo[N]; int top,sui[N]; queue<int> q; char s[N]; void dfs(int now) { sui[++top]=now; for(int i=0;i<26;i++) if(dep[xia[now][i]]==dep[now]+1) dfs(xia[now][i]); top--; if(pre[now]!=1) ans-=num[sui[dep[now]-dep[pre[now]]+1]]-1; } int main() { read(n); tot=1; for(int cas=1;cas<=n;cas++) { scanf("%s",s); int len=strlen(s); for(int i=0,flag=1;i<len;i++)//建立trie树。 { int c=s[i]-'a'; if(!xia[flag][c]) xia[flag][c]=++tot; dep[xia[flag][c]]=dep[flag]+1; flag=xia[flag][c]; } } ans=1ll*(tot-1)*(tot-1); for(int i=0;i<26;++i)//建立trie树上的fail指针。 if(xia[1][i]) { pre[xia[1][i]]=1; q.push(xia[1][i]); } else xia[1][i]=1; for(;!q.empty();)//以fail指针建一棵树，便于下面查找。 { // writeln(66); int flag=q.front(); q.pop(); for(int i=0;i<26;i++) if(xia[flag][i]) { pre[xia[flag][i]]=xia[pre[flag]][i]; q.push(xia[flag][i]); } else xia[flag][i]=xia[pre[flag]][i]; } for(int i=1;i<=tot;i++) cnt[dep[i]]++; for(int i=1;i<=tot;i++) cnt[i]+=cnt[i-1]; for(int i=tot;i;--i) tuo[cnt[dep[i]]--]=i; for(int i=tot;i;--i) { int zz=tuo[i]; ++num[zz]; num[pre[zz]]+=num[zz]; }num[1]=1; dfs(1); writeln(ans); return 0; }

说实话，我写博客好像没人看得懂的样子。