题目链接：
http://www.lydsy.com/JudgeOnline/problem.php?id=3277
http://www.lydsy.com/JudgeOnline/problem.php?id=3473
题意：给定 n 个字符串，询问每个字符串有多少子串（不包括空串）是所有 n 个字符串中至少 k 个字符串的子串？
直接对所有串建广义后缀自动机，如果你看了 clj 的 ppt 并且很熟悉那一套理论，一个状态 s 代表的串的种类数就是\(mx_s-mn_s+1\)。
这个怎么求呢，mx 可以直接处理出来，考虑到\(mn_s=mx_{fa_s}+1\)，所以\(kind_s=mx_s-mx_{fa_s}\)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 100010 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,k; ll ans[N]; char s[N]; struct zgz { int next,to; }edge[N<<1]; int cnt=1,head[N<<1]; void add_e(int from,int to) { edge[cnt].to=to; edge[cnt].next=head[from]; head[from]=cnt++; } namespace SAM { #define M 200010 int ch[M][26],fail[M]; int mx[M],kind[M]; int vis[M],col[M]; int tot=1,last=1; int np,p,q,nq; void add(int x,int t) { np=++tot,p=last; kind[np]=t,last=np,mx[np]=mx[p]+1; while(p&&!ch[p][x])ch[p][x]=np,p=fail[p]; if(p==0){fail[np]=1;return ;} q=ch[p][x]; if(mx[q]==mx[p]+1){fail[np]=q;return ;} nq=++tot,mx[nq]=mx[p]+1,vis[nq]=vis[q],col[nq]=col[q]; memcpy(ch[nq],ch[q],sizeof(ch[q])); fail[nq]=fail[q],fail[q]=fail[np]=nq; while(p&&ch[p][x]==q)ch[p][x]=nq,p=fail[p]; } void Col(int t) { int now=np; while(now&&vis[now]!=t)vis[now]=t,col[now]++,now=fail[now]; } ll sum[M]; void dfs(int x) { if(col[x]>=k)sum[x]=mx[x]-mx[fail[x]]; sum[x]+=sum[fail[x]],ans[kind[x]]+=sum[x]; for(int i=head[x];i;i=edge[i].next) dfs(edge[i].to); } void count() { for(int i=2;i<=tot;i++)add_e(fail[i],i); dfs(1); } } int main() { n=read(),k=read(); for(int i=1;i<=n;i++) { scanf("%s",s+1); int len=strlen(s+1); for(int j=1;j<=len;j++) { SAM::add(s[j]-'a',i); SAM::Col(i); } SAM::last=1; } SAM::count(); for(int i=1;i<=n;i++) printf("%lld ",ans[i]); } |
Comments | NOTHING