[USACO17DEC]Standing Out from the Herd（广义后缀自动机）

题意

定义一个字符串的「独特值」为只属于该字符串的本质不同的非空子串的个数。如 "amy" 与 “tommy” 两个串，只属于 "amy" 的本质不同的子串为 "a" "am" "amy" 共 3 个。只属于 "tommy" 的本质不同的子串为 "t" "to" "tom" "tomm" "tommy" "o" "om" "omm" "ommy" "mm" "mmy" 共 11 个。所以 "amy" 的「独特值」为 3 ，"tommy" 的「独特值」为 11 。

给定 N ( N≤10^5 ) 个字符集为小写英文字母的字符串，所有字符串的长度和小于 10^5 ，求出每个字符串「独特值」。

题解

　　这题和喵星人的点名那题有点像啊……会了那题做这题挺简单的

　　先把所有串一起建一个广义SAM，然后把所有串放上去跑一遍，记录一下每一个子串属于多少个原串。然后再把所有串放上去跑一边，如果这个子串只属于一个原串，那么就把它的答案加上$l[i]-l[fa[i]]$（都是后缀自动机上的节点）

 // luogu-judger-enable-o2

 //minamoto

 #include<cstring>

 #include<cstdio>

 using namespace std;

 char sr[<<],z[];int C=-,Z;

 inline void Ot(){fwrite(sr,,C+,stdout),C=-;}

 inline void print(int x){

     if(C><<)Ot();if(x<)sr[++C]=,x=-x;

     while(z[++Z]=x%+,x/=);

     while(sr[++C]=z[Z],--Z);sr[++C]='\n';

 }

 const int N=1e5+;

 char c[N];int len[N],tot,ans[N],s[N];

 int fa[N<<],ch[N<<][],l[N<<],sz[N<<],las[N<<];

 int n,cnt=,last=;

 void ins(int c){

     int p=last,np=++cnt;last=np,l[np]=l[p]+;

     for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;

     if(!p) fa[np]=;

     else{

         int q=ch[p][c];

         if(l[p]+==l[q]) fa[np]=q;

         else{

             int nq=++cnt;l[nq]=l[p]+;

             memcpy(ch[nq],ch[q],sizeof(ch[q]));

             fa[nq]=fa[q];fa[q]=fa[np]=nq;

             for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;

         }

     }

 }

 void update(int x,int y){

     for(;x&&las[x]!=y;x=fa[x])

     ++sz[x],las[x]=y;

 }

 void query(int x,int y){

     for(;x&&las[x]!=y;x=fa[x]){

         if(sz[x]==) ans[y]+=l[x]-l[fa[x]];

         las[x]=y;

     }

 }

 int main(){

     scanf("%d",&n);

     for(int i=;i<=n;++i){

         scanf("%s",c+);

         len[i]=strlen(c+);

         last=;

         for(int j=;j<=len[i];++j) s[++tot]=c[j]-'a',ins(s[tot]);

     }

     tot=;

     for(int i=;i<=n;++i)

     for(int j=,x=;j<=len[i];++j)

     update(x=ch[x][s[++tot]],i);

     for(int i=;i<=cnt;++i) las[i]=;

     tot=;

     for(int i=;i<=n;++i)

     for(int j=,x=;j<=len[i];++j)

     query(x=ch[x][s[++tot]],i);

     for(int i=;i<=n;++i) print(ans[i]);

     Ot();

     return ;

 }

巴特西

[USACO17DEC]Standing Out from the Herd（广义后缀自动机）

最新文章

热门文章