首页 > 代码库 > Bzoj3277 串

Bzoj3277 串

2024-09-25 11:31:02   215人阅读

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 568  Solved: 233

Description

字符串是oi界常考的问题。现在给定你n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串（注意包括本身）。

Input

第一行两个整数n，k。
　　接下来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 串


联系
我们