【BZOJ3473&BZOJ3277】字符串（广义后缀自动机）

题意：给定n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串？

本质相同的子串算多个。

对于 100% 的数据，1<=n，k<=10^5，所有字符串总长不超过10^5，字符串只包含小写字母。

思路：From 15年国家集训队张天扬论文

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 typedef unsigned int uint;
  5 typedef unsigned long long ull;
  6 typedef pair<int,int> PII;
  7 typedef pair<ll,ll> Pll;
  8 typedef vector<int> VI;
  9 typedef vector<PII> VII;
 10 typedef pair<ll,int>P;
 11 #define N  100010
 12 #define M  210000
 13 #define fi first
 14 #define se second
 15 #define MP make_pair
 16 #define pi acos(-1)
 17 #define mem(a,b) memset(a,b,sizeof(a))
 18 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
 19 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
 20 #define lowbit(x) x&(-x)
 21 #define Rand (rand()*(1<<16)+rand())
 22 #define id(x) ((x)<=B?(x):m-n/(x)+1)
 23 #define ls p<<1
 24 #define rs p<<1|1
 25 
 26 const int MOD=1e9+7,inv2=(MOD+1)/2;
 27       double eps=1e-6;
 28       int INF=1<<29;
 29       ll inf=5e13;
 30       int dx[4]={-1,1,0,0};
 31       int dy[4]={0,0,-1,1};
 32 
 33 string s[N];
 34 int p,np,q,nq,k,cas;
 35 
 36 int read()
 37 {
 38    int v=0,f=1;
 39    char c=getchar();
 40    while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
 41    while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
 42    return v*f;
 43 }
 44 
 45 struct sam
 46 {
 47     int cnt;
 48     int fa[N<<1],t[N<<1][26];
 49     int st[N<<1],b[N<<1],bl[N<<1],c[N<<1];
 50     ll f[N<<1];
 51 
 52     sam()
 53     {
 54         cnt=1;
 55     }
 56 
 57     void add(int x)
 58     {
 59         p=np; st[np=++cnt]=st[p]+1;
 60         while(p&&!t[p][x])
 61         {
 62             t[p][x]=np;
 63             p=fa[p];
 64         }
 65         if(!p) fa[np]=1;
 66          else if(st[p]+1==st[q=t[p][x]]) fa[np]=q;
 67           else
 68           {
 69                   st[nq=++cnt]=st[p]+1;
 70                   memcpy(t[nq],t[q],sizeof t[q]);
 71                   //t[nq]=t[q];
 72                   fa[nq]=fa[q];
 73                   fa[q]=fa[np]=nq;
 74                   while(p&&t[p][x]==q)
 75                   {
 76                       t[p][x]=nq;
 77                       p=fa[p];
 78                   }
 79           }
 80     }
 81 
 82     void solve()
 83     {
 84         rep(i,1,cas)
 85         {
 86             int u=1;
 87             rep(j,0,(int)s[i].size()-1)
 88             {
 89                 int p=u=t[u][s[i][j]-'a'];
 90                 while(p!=1&&b[p]!=i)
 91                 {
 92                     c[p]++; b[p]=i;
 93                     p=fa[p];
 94                 }
 95             }
 96         }
 97         rep(i,0,cnt) b[i]=0;
 98         rep(i,1,cnt) b[st[i]]++;
 99         rep(i,1,cnt) b[i]+=b[i-1];
100         rep(i,1,cnt) bl[b[st[i]]--]=i;
101 
102         rep(i,1,cnt)
103         {
104             int p=bl[i];
105             if(c[p]>=k) f[p]=f[fa[p]]+st[p]-st[fa[p]];
106              else f[p]=f[fa[p]];
107         }
108         rep(i,1,cas)
109         {
110             ll ans=0;
111             int u=1;
112             rep(j,0,(int)s[i].size()-1)
113             {
114                 u=t[u][s[i][j]-'a'];
115                 ans+=f[u];
116             }
117             printf("%lld ",ans);
118         }
119 
120     }
121 }sam;
122 
123 
124 int main()
125 {
126     cas=read(),k=read();
127     rep(v,1,cas)
128     {
129         cin>>s[v];
130         np=1;
131         rep(i,0,(int)s[v].size()-1) sam.add(s[v][i]-'a');
132     }
133     sam.solve();
134     return 0;
135 }