首页 > 代码库 > BZOJ 1396:识别子串 SA+树状数组+单调队列
BZOJ 1396:识别子串 SA+树状数组+单调队列
1396: 识别子串
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 381 Solved: 243
[Submit][Status][Discuss]
Description
Input
一行,一个由小写字母组成的字符串S,长度不超过10^5
Output
L行,每行一个整数,第i行的数据表示关于S的第i个元素的最短识别子串有多长.
Sample Input
agoodcookcooksgoodfood
Sample Output
1
2
3
3
2
2
3
3
2
2
3
3
2
1
2
3
3
2
1
2
3
4
2
3
3
2
2
3
3
2
2
3
3
2
1
2
3
3
2
1
2
3
4
想法：
如果s[i..j]为识别串,s[i-y..j+x]同样也是识别串，可以通过枚举一个端点来得到最短识别串。
设wi=max{lcp(i,j)}+1=max{height[rank[i]],height[rank[i+1]]}+1
s[i..j]为识别子串<==>j-i+1>=wi。
即j>=i+max{height[rank[i]],height[rank[i+1]]}，令hi=i+max{height[rank[i]],height[rank[i+1]]}
即j>=i+max{height[rank[i]],height[rank[i+1]]}，令hi=i+max{height[rank[i]],height[rank[i+1]]}
显然h(i)>h(i-1),ansi=min{max(j-i+1,hi-i+1)}i<=j
ansj=min(j-i+1)hi<=j;树状数组维护
ansj=min(hi-i+1)i<=j,hi>=j;线段树维护或者单调队列。
当 hx-x<hy-y&&x>y,y就无用了.
ansj=min(hi-i+1)i<=j,hi>=j;线段树维护或者单调队列。
当 hx-x<hy-y&&x>y,y就无用了.
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
const int len(100000),limt(255);
int str[len+10],sfa[len+10],rank[len+10],height[len+10];
int tmp[len+10],p[len+10],cnt[len+10];
int n,c[len+10],ans[len+10],q[len+10],li,hi;char ch[len+10];
struct data{int x,y;}h[len+10];
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
bool com(int x,int y,int l){return (rank[x]==rank[y])&&(rank[x+l]==rank[y+l]);}
void doubling()
{
for(int i=1;i<=n;i++){rank[i]=str[i];sfa[i]=i;}
for(int pos=0,l=0,sigma=limt;pos<n;sigma=pos)
{
pos=0;
for(int i=n-l+1;i<=n;i++)p[++pos]=i;
for(int i=1;i<=n;i++)if(sfa[i]>l)p[++pos]=sfa[i]-l;
memset(cnt,0,sizeof(int)*(sigma+1));pos=0;
for(int i=1;i<=n;i++)cnt[rank[i]]++;
for(int i=1;i<=sigma;i++)cnt[i]+=cnt[i-1];
for(int i=n;i>=1;i--)sfa[cnt[rank[p[i]]]--]=p[i];
for(int i=1;i<=n;i++)tmp[sfa[i]]=com(sfa[i],sfa[i-1],l)?pos:++pos;
for(int i=1;i<=n;i++)rank[i]=tmp[i];
l=!l?1:l<<1;
}
for(int i=1;i<=n;i++)rank[sfa[i]]=i;
for(int i=1,k,j;i<=n;i++)
{
k=sfa[rank[i]-1];
if(!k)continue;
j=height[rank[i-1]];
if(j)j--;
while(str[i+j]==str[k+j])j++;
height[rank[i]]=j;
}
}
int query(int x){int sum=0;for(;x;x-=x&(-x))sum=max(sum,c[x]);return sum;}
void put(int x,int y){for(;x<=n;x+=x&(-x))c[x]=max(c[x],y);}
int main()
{
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
scanf("%s",ch);n=strlen(ch);
for(int i=1;i<=n;i++)str[i]=ch[i-1]-‘a‘+1;
doubling();
for(int i=1;i<=n;i++)
{
h[i].x=i+max(height[rank[i]],height[rank[i]+1]);
h[i].y=i;
if(h[i].x>n+1)printf("NO");
}
for(int i=1,t;i<=n;i++)
{
if(h[i].x!=n+1)ans[h[i].y]=h[i].x-h[i].y+1;
else ans[h[i].y]=n;
t=query(h[i].y);
if(t)ans[h[i].y]=min(h[i].y-t+1,ans[h[i].y]);
if(h[i].x!=n+1)put(h[i].x,h[i].y);
}
q[li=1]=1;hi=1;
for(int i=2;i<=n;i++)
{
while(h[q[hi]].x<i&&hi<=li)hi++;
if(hi<=li&&h[q[hi]].x>=i&&h[q[hi]].x!=n+1)ans[h[i].y]=min(ans[h[i].y],h[q[hi]].x-h[q[hi]].y+1);
if(h[i].x!=n+1)
{
while(h[q[li]].x-h[q[li]].y>h[i].x-h[i].y&&li>=hi)li--;
q[++li]=i;
}
}
for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
return 0;
}
BZOJ 1396:识别子串 SA+树状数组+单调队列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。