洛谷P3966 [TJOI2013]单词（后缀自动机）-白红宇

洛谷P3966 [TJOI2013]单词（后缀自动机）

阅读量：6407 次

发布时间：2019-06-23

本文共 1613 字，大约阅读时间需要 5 分钟。

统计单词出现次数……为啥大家都是写AC自动机的嘞……明明后缀自动机也能做的说……

统计出现次数这个就直接按长度排序然后做个dp就好，这是SAM的板子的要求啊，不提了

然后考虑怎么让所有串之间隔开。本来打算建个广义SAM后来发现没办法处理子串重复的情况……然后就按题解里的方法在每两个串之间加入一个新字符然后直接对整个串建好了

1 //minamoto 2 #include
     
       3 #include
      
        4 #include
       
         5 using namespace std; 6 const int N=4e6+5; 7 int fa[N],ch[N][27],l[N],cnt[N],last=1,tot=1; 8 char s[N>>1],t[N>>1];int len[N>>1],c[N],a[N],k,ans[N],n; 9 void ins(int c){10     int p=last,np=++tot;last=np,l[np]=l[p]+1,cnt[np]=1;11     for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;12     if(!p) fa[np]=1;13     else{14         int q=ch[p][c];15         if(l[q]==l[p]+1) fa[np]=q;16         else{17             int nq=++tot;l[nq]=l[p]+1;18             memcpy(ch[nq],ch[q],sizeof(ch[q]));19             fa[nq]=fa[q],fa[q]=fa[np]=nq;20             for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;21         }22     }23 }24 inline void calc(){25     for(int i=1;i<=tot;++i) ++c[l[i]];26     for(int i=1;i<=tot;++i) c[i]+=c[i-1];27     for(int i=1;i<=tot;++i) a[c[l[i]]--]=i;28     for(int i=tot;i;--i) cnt[fa[a[i]]]+=cnt[a[i]];29 }30 int main(){31 //    freopen("testdata.in","r",stdin);32     scanf("%d",&n);33     for(int i=1;i<=n;++i){34         scanf("%s",t+1);len[i]=strlen(t+1);35         for(int j=1;j<=len[i];++j) ins(s[++k]=t[j]-'a');36         ins(s[++k]=26);37     }38     calc();k=0;39     for(int i=1,x,j;i<=n;++i){40         for(j=1,x=1;j<=len[i];++j)41         x=ch[x][s[++k]];42         ans[i]=cnt[x];43         ++k;44     }45     for(int i=1;i<=n;++i) printf("%d\n",ans[i]);46     return 0;47 }