首页 > 代码库 > 【BZOJ3172】【Tjoi2013】单词 AC自动机模板题
【BZOJ3172】【Tjoi2013】单词 AC自动机模板题
转载请注明出处:http://blog.csdn.net/vmurder/article/details/42711351
其实我就是觉得原创的访问量比未授权盗版多有点不爽233。。。
题解:水爆了,直接AC自动机瞎写就行。
坑:……时隔一个半月的感动AC,竟然是因为这道题可以有重复单词233。
代码:
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 1001000 #define M 205 #define T 27 #define inf 0x3f3f3f3f using namespace std; struct KSD { int v,next; }e[M]; int head[N],tot; inline void add(int u,int v) { e[++tot].v=v; e[tot].next=head[u]; head[u]=tot; } char s[N]; int begin[M],end[M],n; // 左闭右开 int ans[N]; struct ACAUTO { int next[N][T],fail[N],flag[N],cnt; void insert(int id,int l,int r) { int i,x,alp; for(x=0,i=l;i<=r;i++) { alp=s[i]-'a'; if(!next[x][alp])next[x][alp]=++cnt; x=next[x][alp]; } add(x,id); } int stk[N],top; void build() { queue<int>q; q.push(0); int i,u,v; while(!q.empty()) { u=q.front(),q.pop(); stk[++top]=u; for(i=0;i<T;i++) { if(v=next[u][i]) { if(!u)fail[v]=0; else fail[v]=next[fail[u]][i]; q.push(v); } else next[u][i]=next[fail[u]][i]; } } } int f[N]; void find() { int i,x,alp; for(i=0;i<end[n];i++) { if(s[i]=='$') { x=0; continue; } alp=s[i]-'a'; f[x=next[x][alp]]++; } } void dp() { int i,u,v; while(top) { u=stk[top--]; for(i=head[u];i;i=e[i].next) ans[e[i].v]+=f[u]; f[fail[u]]+=f[u]; } } }acauto; int main() { // freopen("test.in","r",stdin); int i,j,k; scanf("%d",&n); end[0]=-1; for(i=1;i<=n;i++) { s[++end[i-1]]='$'; begin[i]=end[i-1]+1; scanf("%s",s+begin[i]); end[i]=end[i-1]+strlen(s+begin[i]); acauto.insert(i,begin[i],end[i]); }end[n]++; acauto.build(); acauto.find(); acauto.dp(); for(i=1;i<=n;i++)printf("%d\n",ans[i]); return 0; }
【BZOJ3172】【Tjoi2013】单词 AC自动机模板题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。