3473: 字符串
Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 354 Solved: 160
[Submit][Status][Discuss]
Description
给定n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串？
Input
第一行两个整数n，k。
接下来n行每行一个字符串。
Output
一行n个整数，第i个整数表示第i个字符串的答案。
字符串总长度L
n,k,L<=1e5
研究了两节多课广义后缀自动机是什么，还看了2015国家队论文，然后发现，广义后缀自动机不就是把很多串的SAM建到了一个SAM上，建每个串的时候都从root开始(last=root)就行了........
广义后缀自动机是Trie树的后缀自动机，可以解决多主串问题
这样的在线构造算法复杂度为O(G(T))，G(T)为Trie树上所有叶子节点深度和，发现G(T)<=所有主串总长度
还有一种离线算法，复杂度O(|T||A|) ，不学了吧
对于本题，建出广义SAM后，只要得到每个状态出现在不同串中的次数就好做了
我们跑每个子串，然后更新状态
状态维护cou和cur分别为出现次数及上一次出现是哪个串，然后就可以不重复的统计啦
出现次数向父亲传递，所以要沿着Parent向上跑更新，遇到cur=当前串的就不用继续跑了，这样最坏情况下复杂度为O(L^3/2),发生在n=L的时候(均值不等式啊)
剩下的只要DP出f[i]为i及其Parent祖先出现次数>=k有多少字符串(注意一个状态贡献的字符串为t[par].val-t[u].val)，然后在跑一遍每个字符串得到答案就行了
注意sz也要=1啊啊啊啊啊啊啊啊啊再让你作死写新模板
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
using namespace std;
const int N=2e5+;
typedef long long ll;
int n,k;
string s[N>>];
char ss[N>>];
struct node{
int ch[],par,val;
int cou,cur;
}t[N];
int sz=,root=,last=;
void extend(int c){
int p=last,np=++sz;
t[np].val=t[p].val+;
for(;p&&!t[p].ch[c];p=t[p].par) t[p].ch[c]=np;
if(!p) t[np].par=root;
else{
int q=t[p].ch[c];
if(t[q].val==t[p].val+) t[np].par=q;
else{
int nq=++sz;
t[nq]=t[q];t[nq].val=t[p].val+;
t[q].par=t[np].par=nq;
for(;p&&t[p].ch[c]==q;p=t[p].par) t[p].ch[c]=nq;
}
}
last=np;
}
int c[N],a[N];
ll f[N];
void RadixSort(){
for(int i=;i<=sz;i++) c[t[i].val]++;
for(int i=;i<=sz;i++) c[i]+=c[i-];
for(int i=sz;i>=;i--) a[c[t[i].val]--]=i;
}
void solve(){
int u;ll ans;
for(int i=;i<=n;i++){//printf("i %d\n",i);
u=root;
for(int j=;j<s[i].size();j++){
u=t[u].ch[s[i][j]-'a'];//printf("u %d %d %d\n",u,t[u].cou,j);
int p=u;
for(;p&&t[p].cur!=i;p=t[p].par) t[p].cou++,t[p].cur=i;
}
}
RadixSort();
for(int i=;i<=sz;i++) u=a[i];
t[].cou=;
for(int i=;i<=sz;i++) u=a[i],f[u]=f[t[u].par]+(t[u].cou>=k?t[u].val-t[t[u].par].val:);
for(int i=;i<=n;i++){
u=root;ans=;
for(int j=;j<s[i].size();j++){
u=t[u].ch[s[i][j]-'a'];
ans+=f[u];
}
printf("%lld ",ans);
}
}
int main(){
freopen("in","r",stdin);
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++){
scanf("%s",ss),s[i]=string(ss);
last=root;
for(int j=;j<s[i].size();j++) extend(s[i][j]-'a');
}
solve();
}