首页 > 代码库 > bzoj 3172 后缀数组|AC自动机
bzoj 3172 后缀数组|AC自动机
后缀数组或者AC自动机都可以,模板题。
/************************************************************** Problem: 3172 User: BLADEVIL Language: C++ Result: Accepted Time:424 ms Memory:34260 kb ****************************************************************/ //By BLADEVIL #include <cstdio> #include <cstring> #define maxn 2000010 #define maxm 300 using namespace std; struct node{ int cnt; node *fail,*child[30]; node(){ cnt=0; fail=NULL; memset(child,0,sizeof child); } } *que[maxn],*root=new(node),*w[maxm]; int n; int main(){ scanf("%d",&n); for (int i=1;i<=n;i++){ char c[maxn]; scanf("%s",&c); int len=strlen(c); node *t=root; for (int j=0;j<len;j++){ if (!t->child[c[j]-‘a‘]) t->child[c[j]-‘a‘]=new(node); t=t->child[c[j]-‘a‘]; t->cnt++; } w[i]=t; } int h=0,t=1; root->fail=root; que[1]=root; while (h<t){ node *u=que[++h]; for (int i=0;i<26;i++) if (u->child[i]){ que[++t]=u->child[i]; node *v=u->fail; que[t]->fail=v->child[i]&&v->child[i]!=que[t]?v->child[i]:root; } else u->child[i]=u->fail->child[i]; } for (int i=t;i;i--) que[i]->fail->cnt+=que[i]->cnt; for (int i=1;i<=n;i++) printf("%d\n",w[i]->cnt); return 0; }
/************************************************************** Problem: 3172 User: BLADEVIL Language: C++ Result: Accepted Time:6660 ms Memory:107360 kb ****************************************************************/ //By BLADEVIL #include <cstdio> #include <cstring> #include <algorithm> #define maxn 1001000 #define maxm 300 using namespace std; int n,len; char s[maxn]; int sa[maxn],tsa[maxn],rk[maxn],trk[maxn],sum[maxn],h[maxn]; int w[maxn][21]; int adr[maxm],len_s[maxm]; inline void getsa(int j) { for (int i=1;i<=len;i++) sum[i]=0; for (int i=1;i<=len;i++) sum[rk[i+j]]++; for (int i=1;i<=len;i++) sum[i]+=sum[i-1]; for (int i=len;i;i--) tsa[sum[rk[i+j]]--]=i; for (int i=1;i<=len;i++) sum[i]=0; for (int i=1;i<=len;i++) sum[rk[i]]++; for (int i=1;i<=len;i++) sum[i]+=sum[i-1]; for (int i=len;i;i--) sa[sum[rk[tsa[i]]]--]=tsa[i]; } inline int query(int l,int r) { int i,j; for (i=0,j=1;(j<<1)<=r-l+1;j<<=1,i++) ; return min(w[l][i],w[r-j+1][i]); } int main() { scanf("%d",&n); len=0; for (int i=1;i<=n;i++) { scanf("%s",s+len+1); adr[i]=len+1; len=strlen(s+1); s[++len]=‘^‘; len_s[i]=len-adr[i]; } //for (int i=1;i<=len;i++) printf("%c",s[i]); printf("\n"); for (int i=1;i<=len;i++) sum[s[i]]++; for (int i=1;i<=255;i++) sum[i]+=sum[i-1]; for (int i=len;i;i--) sa[sum[s[i]]--]=i; rk[sa[1]]=1; for (int i=2,p=1;i<=len;i++) { if (s[sa[i]]!=s[sa[i-1]]) p++; rk[sa[i]]=p; } for (int j=1;j<=len;j<<=1) { getsa(j); trk[sa[1]]=1; for (int i=2,p=1;i<=len;i++) { if (rk[sa[i]]!=rk[sa[i-1]]||rk[sa[i]+j]!=rk[sa[i-1]+j]) p++; trk[sa[i]]=p; } for (int i=1;i<=len;i++) rk[i]=trk[i]; } for (int i=1,j=0;i<=len;i++) { if (rk[i]==1) continue; while (i+j<=len&&sa[rk[i]-1]+j<=len&&s[i+j]==s[sa[rk[i]-1]+j]) j++; h[rk[i]]=j; if (j) j--; } //for (int i=1;i<=len;i++) printf("%d ",sa[i]); printf("\n"); //for (int i=1;i<=len;i++) printf("%d ",h[i]); printf("\n"); memset(w,127,sizeof w); for (int i=1;i<=len;i++) w[i][0]=h[i]; for (int j=1,k=1;j<21;j++,k<<=1) for (int i=1;i<=len;i++) if (i+k<=len) w[i][j]=min(w[i][j-1],w[i+k][j-1]); //for (int i=1;i<=len;i++) printf("%d ",w[i][2]); printf("\n"); //printf("%d\n",query(5,8)); //printf("%d\n",rk[6]); for (int i=1;i<=n;i++) { int l=1,r=rk[adr[i]],mid,left=rk[adr[i]],right=rk[adr[i]]; while (l<=r) { mid=l+r>>1; if (query(mid+1,rk[adr[i]])>=len_s[i]) left=mid,r=mid-1; else l=mid+1; } l=rk[adr[i]],r=len; while (l<=r) { mid=l+r>>1; if (query(rk[adr[i]]+1,mid)>=len_s[i]) right=mid,l=mid+1; else r=mid-1; } printf("%d\n",right-left+1); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。