3473: 字符串
Description
给定n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串？Input
第一行两个整数n，k。接下来n行每行一个字符串。Output
一行n个整数，第i个整数表示第i个字符串的答案。Sample Input
3 1
abc
a
abSample Output
6 1 3HINT
对于 100% 的数据，1<=n，k<=10^5，所有字符串总长不超过10^5，字符串只包含小写字母。
【分析】
这道题用后缀数组的被SAM完爆了..貌似...
首先将所有字符串串在一次做SA，然后我们对于sa上，枚举每个串的每个后缀，求出有几个该后缀的前缀符合条件，那么就要判定区间里面有多少个不同的数，所幸的是这里只需要求是否该数目>=k，所以对于每个位置记录个L（x），表示[L(x),x]中刚好有k个不同的数，且L（x）与x距离最大（参考了CF官方题解）。（这里弄几条链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~~
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 200010
#define LL long long int n,k;
char s[Maxn];
int a[Maxn],bl[Maxn],cl; int mymin(int x,int y) {return x<y?x:y;} void init()
{
scanf("%d%d",&n,&k);
cl=;
for(int i=;i<=n;i++)
{
scanf("%s",s+);
int len=strlen(s+);
for(int j=;j<=len;j++) a[++cl]=s[j]-'a'+,bl[cl]=i;
a[++cl]=,bl[cl]=-;
}
} int sa[Maxn],y[Maxn],rk[Maxn],Rs[Maxn],wr[Maxn];
void get_sa(int m)
{
memcpy(rk,a,sizeof(rk));
for(int i=;i<=m;i++) Rs[i]=;
for(int i=;i<=cl;i++) Rs[rk[i]]++;
for(int i=;i<=m;i++) Rs[i]+=Rs[i-];
for(int i=cl;i>=;i--) sa[Rs[rk[i]]--]=i; int ln=,p=;
while(p<cl)
{
int k=;
for(int i=cl-ln+;i<=cl;i++) y[++k]=i;
for(int i=;i<=cl;i++) if(sa[i]>ln) y[++k]=sa[i]-ln;
for(int i=;i<=cl;i++) wr[i]=rk[y[i]]; for(int i=;i<=m;i++) Rs[i]=;
for(int i=;i<=cl;i++) Rs[wr[i]]++;
for(int i=;i<=m;i++) Rs[i]+=Rs[i-];
for(int i=cl;i>=;i--) sa[Rs[wr[i]]--]=y[i]; // memcpy(wr,rk,sizeof(wr));
for(int i=;i<=cl;i++) wr[i]=rk[i];
for(int i=cl+;i<=cl+ln;i++) wr[i]=;
p=;
rk[sa[]]=;
for(int i=;i<=cl;i++)
{
if(wr[sa[i]]!=wr[sa[i-]]||wr[sa[i]+ln]!=wr[sa[i-]+ln]) p++;
rk[sa[i]]=p;
} ln*=;m=p;
}
} int height[Maxn];
void get_he()
{
int kk=;
for(int i=;i<=cl;i++) if(rk[i]!=)
{
int j=sa[rk[i]-];
if(kk) kk--;
while(a[i+kk]==a[j+kk]&&i+kk<=cl&&j+kk<=cl) kk++;
height[rk[i]]=kk;
}
} int g[Maxn],lt[Maxn],nt[Maxn],sm[Maxn];
bool p[Maxn];
void get_g()
{
memset(lt,,sizeof(lt));
for(int i=;i<=cl;i++)
{
sm[i]=lt[bl[sa[i]]];
lt[bl[sa[i]]]=i;
}
memset(lt,,sizeof(lt));
memset(p,,sizeof(p));
int h=,now;
for(int i=;i<=cl;i++)
{
if(!p[bl[sa[i]]]) h++;
p[bl[sa[i]]]=;
if(h==k) {now=i;break;}
}int id=;
for(int i=now;i>=;i--)
{
if(p[bl[sa[i]]])
{
h--;
if(id)
{
nt[i]=id;lt[id]=i;lt[i]=;
}
id=i;
p[bl[sa[i]]]=;
}
if(h==) {g[now]=i;break;}
}
for(int i=now+;i<=cl;i++)
{
if(sm[i]>g[i-])
{
g[i]=g[i-];
nt[now]=i;lt[i]=now;
nt[lt[sm[i]]]=nt[sm[i]];
lt[nt[sm[i]]]=lt[sm[i]];
}
else
{
nt[now]=i;lt[i]=now;
g[i]=nt[g[i-]];
}
now=i;
}
} int d[Maxn][];
void init_rmq()
{
for(int i=;i<=cl;i++) d[i][]=height[i];
for(int j=;(<<j)<=cl;j++)
for(int i=;i+(<<j)-<=cl;i++)
d[i][j]=mymin(d[i][j-],d[i+(<<j-)][j-]);
} int rmq(int l,int r)
{
int i=;
while(l+(<<i)-<=r) i++;
return mymin(d[l][i-],d[r-(<<i-)+][i-]);
} int t_div(int l,int r,int x,int kk)
{
if(l>r) return x;
while(l<r)
{
int mid;
if(r<x)
{
mid=(l+r)>>;
if(rmq(mid+,x)>=kk) r=mid;
else l=mid+;
}
else
{
mid=(l+r+)>>;
if(rmq(x+,mid)>=kk) l=mid;
else r=mid-;
}
}
if(l<x&&rmq(l+,x)>=kk) return l;
if(l>x&&rmq(x+,l)>=kk) return l;
return x;
} LL ans[Maxn];
void ffind()
{
memset(ans,,sizeof(ans));
int mx=;
for(int i=;i<=cl;i++) if(bl[i]!=-)
{
int kk=;
if(mx>=i) kk=mx-i+;
while()
{
int l=t_div(,rk[i]-,rk[i],kk),r=t_div(rk[i]+,cl,rk[i],kk);
if(g[r]<l||bl[i+kk-]!=bl[i]||i+kk->cl) {kk--;break;}
kk++;
}
ans[bl[i]]+=kk;
mx=i+kk-;
}
} int main()
{
init();
get_sa();
get_he();
get_g();
init_rmq();
ffind();
for(int i=;i<=n;i++)
{
if(i!=) printf(" ");
printf("%lld",ans[i]);
}
return ;
}
[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，大概是机上有原串吧~
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<set>
using namespace std;
#define Maxn 100010
#define LL long long char s[Maxn],ss[Maxn];
int l,bg[Maxn]; struct node
{
int pre,son[],step;
}t[*Maxn];int tot=;
int last; set<int > d[*Maxn]; void upd(int x)
{
memset(t[x].son,,sizeof(t[x].son));
d[x].clear();
t[x].pre=;
} void get_d(int x,int y)
{
if(x==) return;
set<int>:: iterator st,ed;
st=d[y].begin();
ed=d[y].end();
while(st!=ed)
{
d[x].insert(*st);
st++;
}
} void extend(int x,int k)
{
int np=++tot;
upd(np);d[np].insert(x);
t[np].step=t[last].step+;
int now=last;
while(now&&!t[now].son[k])
{
t[now].son[k]=np;
now=t[now].pre;
}
if(!now) t[np].pre=;
else
{
int p=now,q=t[now].son[k];
if(t[p].step+==t[q].step) t[np].pre=q;
else
{
int nq=++tot;
upd(nq);
memcpy(t[nq].son,t[q].son,sizeof(t[nq].son));
get_d(nq,q);
t[nq].pre=t[q].pre;
t[q].pre=t[np].pre=nq;
t[nq].step=t[p].step+;
while(now&&t[now].son[k]==q)
{
t[now].son[k]=nq;
now=t[now].pre;
}
}
}
last=np;
} int n,kk;
void init()
{
scanf("%d%d",&n,&kk);
t[++tot].step=;
upd(tot);
int sl=;
for(int i=;i<=n;i++)
{
scanf("%s",ss+);
l=strlen(ss+);
last=;
bg[i]=sl+;
for(int j=;j<=l;j++)
{
int k=ss[j]-'a'+;
extend(i,k);
s[++sl]=ss[j];
}
}
bg[n+]=sl+;
} struct hp
{
int x,y,next;
}a[*Maxn];int al=;
int first[*Maxn]; void ins(int x,int y)
{
a[++al].x=x;a[al].y=y;
a[al].next=first[x];first[x]=al;
} void dfs(int x)
{
for(int i=first[x];i;i=a[i].next)
{
dfs(a[i].y);
get_d(x,a[i].y);
}
} int main()
{
init();
memset(first,,sizeof(first));
for(int i=;i<=tot;i++) ins(t[i].pre,i);
dfs();
bool ok=;
for(int i=;i<=n;i++)
{
int now=;
LL ans=;
for(int j=bg[i];j<bg[i+];j++)
{
int k=s[j]-'a'+;
now=t[now].son[k];
while(now&&d[now].size()<kk) now=t[now].pre;
if(!now) now=;
ans+=t[now].step;
}
if(!ok) printf(" ");
else ok=;
printf("%lld",ans);
}
return ;
}
[BZOJ 3473]
2016-09-20 21:28:28