【BZOJ 3473】字符串 (后缀数组+RMQ+二分

【BZOJ 3473】字符串 (后缀数组+RMQ+二分 | 广义SAM)

阅读量：4312 次

发布时间：2019-06-06

本文共 6328 字，大约阅读时间需要 21 分钟。

3473: 字符串

Description

给定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% 的数据，1<=n，k<=10^5，所有字符串总长不超过10^5，字符串只包含小写字母。

【分析】

　　这道题用后缀数组的被SAM完爆了..貌似...

首先将所有字符串串在一次做SA，然后我们对于sa上，枚举每个串的每个后缀，求出有几个该后缀的前缀符合条件，那么就要判定区间里面有多少个不同的数，所幸的是这里只需要求是否该数目>=k，所以对于每个位置记录个L（x），表示[L(x),x]中刚好有k个不同的数，且L（x）与x距离最大（参考了）。（这里弄几条链O（n）可以搞出来）

　　然后CF上的题解是对于每个后缀二分出长度l，在排好序的后缀上查找最前最后端点使min（这一段的height）>=l。 （这里用到二分+RMQ）

　　接下来是去掉一个log的优化：（即1上面的二分长度l改成直接从上一个的位置开始for）

那么我们发现枚举后缀的时候，如果后缀c+S有n个前缀合法（c表示一个字符，s表示一个串），那么对于后缀S，至少有n-1个前缀合法（如果c+S有n个前缀出现不小于k次，那么其子串也是），那么我们就用类似求SA里的height一样的方法，记录一下前面的后缀的合法前缀数，然后这样的总复杂度就成了均摊。

搬运：

　　类似求height的那个优化好厉害！！！

　　记得用long long~~

代码如下：

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 #include
           
              6 #include
            
              7 using namespace std; 8 #define Maxn 200010 9 #define LL long long 10 11 int n,k; 12 char s[Maxn]; 13 int a[Maxn],bl[Maxn],cl; 14 15 int mymin(int x,int y) { return x
             
              =1;i--) sa[Rs[rk[i]]--]=i; 38 39 int ln=1,p=1; 40 while(p
              
               ln) y[++k]=sa[i]-ln; 45 for(int i=1;i<=cl;i++) wr[i]=rk[y[i]]; 46 47 for(int i=0;i<=m;i++) Rs[i]=0; 48 for(int i=1;i<=cl;i++) Rs[wr[i]]++; 49 for(int i=1;i<=m;i++) Rs[i]+=Rs[i-1]; 50 for(int i=cl;i>=1;i--) sa[Rs[wr[i]]--]=y[i]; 51 52 // memcpy(wr,rk,sizeof(wr)); 53 for(int i=1;i<=cl;i++) wr[i]=rk[i]; 54 for(int i=cl+1;i<=cl+ln;i++) wr[i]=0; 55 p=1; 56 rk[sa[1]]=1; 57 for(int i=2;i<=cl;i++) 58 { 59 if(wr[sa[i]]!=wr[sa[i-1]]||wr[sa[i]+ln]!=wr[sa[i-1]+ln]) p++; 60 rk[sa[i]]=p; 61 } 62 63 ln*=2;m=p; 64 } 65 } 66 67 int height[Maxn]; 68 void get_he() 69 { 70 int kk=0; 71 for(int i=1;i<=cl;i++) if(rk[i]!=1) 72 { 73 int j=sa[rk[i]-1]; 74 if(kk) kk--; 75 while(a[i+kk]==a[j+kk]&&i+kk<=cl&&j+kk<=cl) kk++; 76 height[rk[i]]=kk; 77 } 78 } 79 80 int g[Maxn],lt[Maxn],nt[Maxn],sm[Maxn]; 81 bool p[Maxn]; 82 void get_g() 83 { 84 memset(lt,0,sizeof(lt)); 85 for(int i=1;i<=cl;i++) 86 { 87 sm[i]=lt[bl[sa[i]]]; 88 lt[bl[sa[i]]]=i; 89 } 90 memset(lt,0,sizeof(lt)); 91 memset(p,0,sizeof(p)); 92 int h=0,now; 93 for(int i=1;i<=cl;i++) 94 { 95 if(!p[bl[sa[i]]]) h++; 96 p[bl[sa[i]]]=1; 97 if(h==k) {now=i;break;} 98 }int id=0; 99 for(int i=now;i>=1;i--)100 {101 if(p[bl[sa[i]]])102 {103 h--;104 if(id)105 {106 nt[i]=id;lt[id]=i;lt[i]=0;107 }108 id=i;109 p[bl[sa[i]]]=0;110 }111 if(h==0) {g[now]=i;break;}112 }113 for(int i=now+1;i<=cl;i++)114 {115 if(sm[i]>g[i-1])116 {117 g[i]=g[i-1];118 nt[now]=i;lt[i]=now;119 nt[lt[sm[i]]]=nt[sm[i]];120 lt[nt[sm[i]]]=lt[sm[i]];121 }122 else123 {124 nt[now]=i;lt[i]=now;125 g[i]=nt[g[i-1]];126 }127 now=i;128 }129 }130 131 int d[Maxn][20];132 void init_rmq()133 {134 for(int i=2;i<=cl;i++) d[i][0]=height[i];135 for(int j=1;(1<
               
                <=cl;j++)136 for(int i=2;i+(1<
                
                 <=cl;i++)137 d[i][j]=mymin(d[i][j-1],d[i+(1<
                 
                  r) return x;150 while(l
                  
                   >1;156 if(rmq(mid+1,x)>=kk) r=mid;157 else l=mid+1;158 }159 else160 {161 mid=(l+r+1)>>1;162 if(rmq(x+1,mid)>=kk) l=mid;163 else r=mid-1;164 }165 }166 if(l
                   
                    =kk) return l;167 if(l>x&&rmq(x+1,l)>=kk) return l;168 return x;169 }170 171 LL ans[Maxn];172 void ffind()173 {174 memset(ans,0,sizeof(ans));175 int mx=0;176 for(int i=1;i<=cl;i++) if(bl[i]!=-1)177 {178 int kk=1;179 if(mx>=i) kk=mx-i+2;180 while(1)181 {182 int l=t_div(1,rk[i]-1,rk[i],kk),r=t_div(rk[i]+1,cl,rk[i],kk);183 if(g[r]
                    
                     cl) {kk--;break;}184 kk++;185 }186 ans[bl[i]]+=kk;187 mx=i+kk-1;188 }189 }190 191 int main()192 {193 init();194 get_sa(30);195 get_he();196 get_g();197 init_rmq();198 ffind();199 for(int i=1;i<=n;i++) 200 {201 if(i!=1) printf(" ");202 printf("%lld",ans[i]);203 }204 return 0;205 }

[BZOJ2473]

2016-08-25 12:00:01

　　233学了广义SAM的我回来更新这题了~~

　　其实我还不是很懂。。

　　看GDXB的题解：

每个节点维护一个set，存它是哪个串的，然后整理一下parent tree从下往上合并set（他们说是启发式合并，然而我用了最普通的暴力合并）。
最后每一个串在自动机上跑一遍，如果set的size<k就不断跳pre，保证当前的这一条后缀的前缀都是可行的，每个可行点的贡献是step[i]。

　　广义SAM不能用step或者son求拓扑序，这个的pre更新用dfs即可。（蒟蒻表示又被坑了！）

　　统计答案的时候可以用step，大概是机上有原串吧~

代码如下：

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 #include
           
              6 #include
            
              7 #include
             
               8 #include
              
                9 using namespace std; 10 #define Maxn 100010 11 #define LL long long 12 13 char s[Maxn],ss[Maxn]; 14 int l,bg[Maxn]; 15 16 struct node 17 { 18 int pre,son[30],step; 19 }t[2*Maxn];int tot=0; 20 int last; 21 22 set
               
                 d[2*Maxn]; 23 24 void upd(int x) 25 { 26 memset(t[x].son,0,sizeof(t[x].son)); 27 d[x].clear(); 28 t[x].pre=0; 29 } 30 31 void get_d(int x,int y) 32 { 33 if(x==0) return; 34 set
                
                 :: iterator st,ed; 35 st=d[y].begin(); 36 ed=d[y].end(); 37 while(st!=ed) 38 { 39 d[x].insert(*st); 40 st++; 41 } 42 } 43 44 void extend(int x,int k) 45 { 46 int np=++tot; 47 upd(np);d[np].insert(x); 48 t[np].step=t[last].step+1; 49 int now=last; 50 while(now&&!t[now].son[k]) 51 { 52 t[now].son[k]=np; 53 now=t[now].pre; 54 } 55 if(!now) t[np].pre=1; 56 else 57 { 58 int p=now,q=t[now].son[k]; 59 if(t[p].step+1==t[q].step) t[np].pre=q; 60 else 61 { 62 int nq=++tot; 63 upd(nq); 64 memcpy(t[nq].son,t[q].son,sizeof(t[nq].son)); 65 get_d(nq,q); 66 t[nq].pre=t[q].pre; 67 t[q].pre=t[np].pre=nq; 68 t[nq].step=t[p].step+1; 69 while(now&&t[now].son[k]==q) 70 { 71 t[now].son[k]=nq; 72 now=t[now].pre; 73 } 74 } 75 } 76 last=np; 77 } 78 79 int n,kk; 80 void init() 81 { 82 scanf("%d%d",&n,&kk); 83 t[++tot].step=0; 84 upd(tot); 85 int sl=0; 86 for(int i=1;i<=n;i++) 87 { 88 scanf("%s",ss+1); 89 l=strlen(ss+1); 90 last=1; 91 bg[i]=sl+1; 92 for(int j=1;j<=l;j++) 93 { 94 int k=ss[j]-'a'+1; 95 extend(i,k); 96 s[++sl]=ss[j]; 97 } 98 } 99 bg[n+1]=sl+1;100 }101 102 struct hp103 {104 int x,y,next;105 }a[2*Maxn];int al=0;106 int first[2*Maxn];107 108 void ins(int x,int y)109 {110 a[++al].x=x;a[al].y=y;111 a[al].next=first[x];first[x]=al;112 }113 114 void dfs(int x)115 {116 for(int i=first[x];i;i=a[i].next)117 {118 dfs(a[i].y);119 get_d(x,a[i].y);120 }121 }122 123 int main()124 {125 init();126 memset(first,0,sizeof(first));127 for(int i=1;i<=tot;i++) ins(t[i].pre,i);128 dfs(1);129 bool ok=1;130 for(int i=1;i<=n;i++)131 {132 int now=1;133 LL ans=0;134 for(int j=bg[i];j