BZOJ3172 [TJOI2013]单词

2014.12.09 13:28 Tue| 8 visits oi_2015| 2015_刷题日常| Text

据说这道题就是传说中的怎么做都能A的神题>_<,KMP/AC自动机/后缀数组/后缀自动机……

Solution

今天快乐地写了一个后缀数组版的,结果一直在WA……后来花了一中午把A掉的程序改得和自己的几乎一模一样,最后发现似乎可能有大写字母,既然这样为什么在wikioi上只错了一组数据 QAQ……。用大号交题的时候还手滑点进去了WTY小朋友刚刚MLE的题,get到了一只OLE……

2014-12-12:

其实是后缀数组模板当时写错了,但是为什么把分隔符从'z'+1改成'$'就A掉了?2333

不论怎样,这道题解法真的很好想的说。处理出height数组,然后枚举单词,在每个单词开头位置后缀的rank处向两侧扩展。这种做法似乎有被卡常数的危险,可以使用RMQ快速求解,但是弱爆了的数据证明完全不需要担心任何事情……

Code

#include <bits/stdc++.h>
using namespace std;
#define N 1000205

char str[N];
int t,pos[205],n,m,x[N],y[N],c[N],sa[N],rank[N],height[N];

inline bool same(int a,int b,int k)
{
    return y[a]==y[b] && ((a+k>=n&&b+k>=n)||(a+k<n&&b+k<n&&y[a+k]==y[b+k]));
}

void get_sa(int m=256)
{
    for(int i=0;i<n;i++) c[x[i]=str[i]]++;
    for(int i=1;i<m;i++) c[i]+=c[i-1];
    for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
    for(int k=1;k<n;k<<=1)
    {
        int p=0;
        for(int i=n-k;i<n;i++) y[p++]=i;
        for(int i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
        memset(c,0,m*sizeof(int));
        for(int i=0;i<n;i++) c[x[y[i]]]++;
        for(int i=1;i<m;i++) c[i]+=c[i-1];
        for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
        for(int i=0;i<n;i++) y[i]=x[i];
        m=0; x[sa[0]]=0;
        for(int i=1;i<n;i++)
            x[sa[i]]=same(sa[i-1],sa[i],k)?m:++m;
        if(++m==n) break;
    }
}

void get_height()
{
    for(int i=0;i<n;i++) rank[sa[i]]=i;
    for(int i=0,j,k=0;i<n;height[rank[i++]]=k)
        if(rank[i]) for(k?k--:0,j=sa[rank[i]-1];str[i+k]==str[j+k];k++);
}

int main()
{
    cin>>t;
    scanf("%s",str);
    for(int i=2;i<=t;i++)
        pos[i]=strlen(str)+1, str[pos[i]-1]='z'+1, scanf("%s",str+pos[i]);
    n=strlen(str);pos[t+1]=n+1;
    get_sa();
    get_height();
    for(int i=1,j;i<=t;i++)
    {
        int ans=0;
        j=rank[pos[i]];
        while(j&&height[j]>=pos[i+1]-pos[i]-1) j--;
        while(height[j+1]>=pos[i+1]-pos[i]-1) j++,ans++;
        cout<<ans+1<<endl;
    }
}