对多串建立 SAM 的一种方法是加分隔符. 于是加完分隔符建出 SAM.
考虑统计出每个节点被多少个串包含. 让每个串各自在 SAM 上跑, 跑到一个节点就标记 (显然一定会完全匹配该节点, 因为是对包含其的串建的 SAM) 并暴跳 fail, 遇到已经被该串标记过的点就停止.
这样暴力的复杂度容易感性证明是 O(Lsqrt(L)), 因为暴力一个串的过程中, SAM 每个点至多被标记一次, 每一步跳 fail 的次数也显然不会超过该串长度, 于是对该串的复杂度是 min(L,|S|2), 总的最劣复杂度大约就是 sqrt(L)个长度为 sqrt(L)的串时取得, 且常数极小. 当然也可以使用树剖实现, 不用分析复杂度就能知道是 O(Llog2L).
然后递推求出每个点被经过时的具体贡献, 也即其到 parent 树的根的路径上所有出现在至少 k 个串中的点的 len-lenfa 值的和. 再对每个串各自跑一遍累加所经过点的贡献即可.
- #include<iostream>
- #include<cstdio>
- #include<cmath>
- #include<cstdlib>
- #include<cstring>
- #include<algorithm>
- #include<vector>
- using namespace std;
- #define ll long long
- #define N 400010
- char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
- int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
- int read()
- {
- int x=0,f=1;char c=getchar();
- while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
- while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
- return x*f;
- }
- int n,m,k,s[N],l[N],r[N],son[N][27],q[N],tot[N],fail[N],len[N],f[N],g[N],cnt=1,last=1;
- char qwq[N];
- bool flag[N];
- vector<int> a;
- void ins(int c)
- {
- int x=++cnt,p=last;last=x;len[x]=len[p]+1;
- while (!son[p][c]&&p) son[p][c]=x,p=fail[p];
- if (!p) fail[x]=1;
- else
- {
- int q=son[p][c];
- if (len[q]==len[p]+1) fail[x]=q;
- else
- {
- int y=++cnt;
- len[y]=len[p]+1;
- memcpy(son[y],son[q],sizeof(son[q]));
- fail[y]=fail[q],fail[x]=fail[q]=y;
- while (son[p][c]==q) son[p][c]=y,p=fail[p];
- }
- }
- }
- int main()
- {
- #ifndef ONLINE_JUDGE
- freopen("a.in","r",stdin);
- freopen("a.out","w",stdout);
- const char LL[]="%I64d";
- #else
- const char LL[]="%lld";
- #endif
- n=read(),k=read();
- for (int i=1;i<=n;i++)
- {
- scanf("%s",qwq+1);
- int _=strlen(qwq+1);
- l[i]=m+1,r[i]=m+_;
- for (int j=1;j<=_;j++) s[++m]=qwq[j]-'a';
- s[++m]=26;
- }
- for (int i=1;i<=m;i++) ins(s[i]);
- for (int i=1;i<=n;i++)
- {
- int k=1;
- for (int j=l[i];j<=r[i];j++)
- {
- while (!son[k][s[j]]) k=fail[k];
- if (!k) k=1;
- else
- {
- k=son[k][s[j]];
- for (int x=k;!flag[x];x=fail[x])
- flag[x]=1,f[x]++,a.push_back(x);
- }
- }
- for (int j:a) flag[j]=0;a.clear();
- }
- for (int i=1;i<=cnt;i++) tot[len[i]]++;
- for (int i=1;i<=m;i++) tot[i]+=tot[i-1];
- for (int i=1;i<=cnt;i++) q[tot[len[i]]--]=i;
- for (int i=1;i<=cnt;i++)
- {
- int x=q[i];
- g[x]=g[fail[x]];
- if (f[x]>=k) g[x]+=len[x]-len[fail[x]];
- }
- for (int i=1;i<=n;i++)
- {
- ll ans=0;int k=1;
- for (int j=l[i];j<=r[i];j++)
- {
- while (!son[k][s[j]]) k=fail[k];
- if (!k) k=1;
- else k=son[k][s[j]],ans+=g[k];
- }
- printf(LL,ans);
- }
- return 0;
- }
BZOJ3277 串(后缀自动机)
来源: http://www.bubuko.com/infodetail-3049381.html