注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2865/1396]字符串识别  

2015-03-16 20:53:26|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2865: 字符串识别

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 167  Solved: 59
[Submit][Status][Discuss]

Description

XX在进行字符串研究的时候,遇到了一个十分棘手的问题。

在这个问题中,给定一个字符串S,与一个整数K,定义S的子串T=S(i, j)是关于第K位的识别子串,满足以下两个条件:

1、iKj

2、子串T只在S中出现过一次。

例如,S="banana"K=5,则关于第K位的识别子串有"nana""anan""anana""nan""banan""banana"

现在,给定SXX希望知道对于S的每一位,最短的识别子串长度是多少,请你来帮助他。

Input

仅一行,输入长度为N的字符串S

Output

输出N行,每行一个整数,第i行的整数表示对于第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

HINT

N<=5*10^5

Solution

用后缀数组先求出sa和height两个数组
假设S=‘banana’,下标从1开始
sa长这样:
6 a
4 ana
2 anana
1 banana
5 na
3 nana
显然两个相邻的串长>=lcp+1时才有可能成为“识别子串”
比如anan,anana,b,ba,ban,...,banana,nan,nana这些
不妨固定左端点,考虑以l为起点的串对答案造成的影响。
当l=2时,anan是最小的识别子串(长度=height+1)对2~5的4个位置都是这么多,然后是anana,...(如果后面还有的话)6位贡献为5.
容易发现,有一个分界点,在(l,x)内均为height+1,在(x+1,n)内是一个公差为1的等差数列。
于是用两颗线段树维护相关标记,最后一次性pushdown输出就行了。

Code

/**************************************************************
    Problem: 1396
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:916 ms
    Memory:9784 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#define N 200010
char s[N];int n,m=26,i,j,k,yt,X[N],Y[N],c[N],*x=X,*y=Y,*T,sa[N],rk[N],hei[N];
int t0[1<<19],x0,y0,key,t1[1<<19];
#define cmp(u,v) (x[u]!=x[v]||x[u+k]!=x[v+k])
#define cmin(a,b) (a>b?a=b:1)
#define min(a,b) (a<b?a:b)
void up(int*t,int o,int l,int r){
    if(x0<=l&&r<=y0){
        cmin(t[o],key);return;
    }
    int mid=l+r>>1;
    cmin(t[o<<1],t[o]),cmin(t[o<<1|1],t[o]);
    if(x0<=mid)up(t,o<<1,l,mid);
    if(mid<y0)up(t,o<<1|1,mid+1,r);
}
void add(int*t,int l,int r,int x){
    x0=l,y0=r,key=x,up(t,1,1,n);
}
void pr(int o,int l,int r){
    if(l==r)printf("%d\n",min(t0[o],t1[o]+l));
    else{
        int mid=l+r>>1;
        cmin(t0[o<<1],t0[o]);cmin(t1[o<<1],t1[o]);pr(o<<1,l,mid);
        cmin(t0[o<<1|1],t0[o]);cmin(t1[o<<1|1],t1[o]);pr(o<<1|1,mid+1,r);
    }
}
int main(){
    for(gets(s+1),n=1;s[n];n++);n--;
    for(i=1;i<=n;i++)c[x[i]=s[i]-'a'+1]++;
    for(i=1;i<=m;i++)c[i]+=c[i-1];
    for(i=n;i;i--)sa[c[x[i]]--]=i;
    for(k=1;k<n&&(k==1||m<n);k<<=1,T=x,x=y,y=T){
        for(yt=0,i=n-k+1;i<=n;i++)y[++yt]=i;
        for(i=1;i<=n;i++)if(sa[i]>k)y[++yt]=sa[i]-k;
        for(i=1;i<=m;i++)c[i]=0;
        for(i=1;i<=n;i++)c[x[i]]++;
        for(i=1;i<=m;i++)c[i]+=c[i-1];
        for(i=n;i;i--)sa[c[x[y[i]]]--]=y[i];
        for(m=0,i=1;i<=n;i++)y[sa[i]]=i==1||cmp(sa[i],sa[i-1])?++m:m;
    }
    for(i=1;i<=n;i++)rk[sa[i]]=i;
    for(i=1,k=0;i<=n;hei[rk[i++]]=k)
    for(k?k--:0,j=sa[rk[i]-1];s[i+k]==s[j+k];k++);
    memset(t0,63,sizeof(t0));
    memset(t1,63,sizeof(t1));
    for(i=1;i<=n;i++){
        j=hei[i]>hei[i+1]?hei[i]+1:hei[i+1]+1;
        if(j+sa[i]-1<=n)add(t0,sa[i],j+sa[i]-1,j);
        add(t1,j+sa[i],n,1-sa[i]);
    }
    pr(1,1,n);
}

  评论这张
 
阅读(404)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018