首页 > 代码库 > Bzoj3277 串
Bzoj3277 串
Submit: 568 Solved: 233
Description
字符串是oi界常考的问题。现在给定你n个字符串,询问每个字符串有多少子串(不包括空串)是所有n个字符串中至少k个字符串的子串(注意包括本身)。
Input
第一行两个整数n,k。
接下来n行每行一个字符串。
接下来n行每行一个字符串。
Output
输出一行n个整数,第i个整数表示第i个字符串的答案。
Sample Input
3 1
abc
a
ab
Sample Output
6 1 3
HINT
对于100%的数据,n,k,l<=100000
Source
后缀数组
广义后缀自动机
把所有串建成广义后缀自动机,开一个size数组记录每个结点被多少个串经过。
若一个结点x的size>=k,则它有maxlen[x]-maxlen[fa[x]](即right集合大小)个贡献,否则贡献为0
从自动机root开始DFS一遍,累计每个点的贡献。
对于每个串,用它在自动机上跑一遍,累计所有经过的点的贡献,即是答案。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #include<vector> 7 #define LL long long 8 using namespace std; 9 const int mxn=200011; 10 int read(){ 11 int x=0,f=1;char ch=getchar(); 12 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 13 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 14 return x*f; 15 } 16 struct edge{ 17 int v,nxt; 18 }e[mxn<<1]; 19 int hd[mxn],mct=0; 20 void add_edge(int u,int v){ 21 e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct; 22 return; 23 } 24 vector<int>ve[mxn>>1]; 25 int n,K; 26 int id; 27 struct SAM{ 28 int t[mxn][26]; 29 int fa[mxn],mx[mxn];LL sz[mxn]; 30 int w[mxn],rk[mxn]; 31 int nxt[mxn]; 32 int S,last,cnt; 33 void init(){S=last=cnt=1;return;} 34 void add(int c){ 35 // printf("add:%d\n",c); 36 int np=++cnt,p=last;last=np; 37 mx[np]=mx[p]+1; 38 for(;p && !t[p][c];p=fa[p])t[p][c]=np; 39 if(!p){fa[np]=S;} 40 else{ 41 int q=t[p][c]; 42 if(mx[q]==mx[p]+1)fa[np]=q; 43 else{ 44 int nq=++cnt;mx[nq]=mx[p]+1; 45 memcpy(t[nq],t[q],sizeof t[q]); 46 sz[nq]=sz[q];nxt[nq]=nxt[q]; 47 fa[nq]=fa[q]; 48 fa[q]=fa[np]=nq; 49 for(;p && t[p][c]==q;p=fa[p])t[p][c]=nq; 50 } 51 } 52 ve[id].push_back(np); 53 while(np){ 54 if(nxt[np]!=id){++sz[np];nxt[np]=id;np=fa[np];} 55 else break; 56 } 57 return; 58 } 59 void ST(){ 60 for(int i=1;i<=cnt;i++)++w[mx[i]]; 61 for(int i=1;i<=cnt;i++)w[i]+=w[i-1]; 62 for(int i=cnt;i;i--)rk[w[mx[i]]--]=i; 63 for(int i=1;i<=cnt;i++){ 64 int r=rk[i]; 65 add_edge(fa[r],r); 66 sz[r]=(sz[r]>=K)?mx[r]-mx[fa[r]]:0; 67 } 68 return; 69 } 70 void DFS(int u){ 71 sz[u]+=sz[fa[u]]; 72 for(int i=hd[u];i;i=e[i].nxt) 73 DFS(e[i].v); 74 return; 75 } 76 }sa; 77 char s[mxn]; 78 int main(){ 79 int i,j; 80 n=read();K=read(); 81 sa.init(); 82 for(i=1;i<=n;i++){ 83 scanf("%s",s+1); 84 int len=strlen(s+1); 85 id=i; 86 for(j=1;j<=len;j++)sa.add(s[j]-‘a‘); 87 sa.last=sa.S; 88 } 89 sa.ST(); 90 sa.DFS(1); 91 sa.sz[sa.S]=0; 92 LL ans=0; 93 for(i=1;i<=n;i++){ 94 ans=0;int ed=ve[i].size(); 95 for(j=0;j<ed;j++){ 96 ans+=sa.sz[ve[i][j]]; 97 } 98 printf("%lld ",ans); 99 }100 return 0;101 }102
Bzoj3277 串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。