Cptraser/ 二月 28, 2019/ 2019.2/ 0 comments

[TJOI2013]单词

题面传送门

用特殊字符把所有串接在一起,然后在SA上二分,输出区间长度即可。

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int Maxn=2e6+5;
int M,N,len,Sz=26;string s[505];int P[Maxn];
int rak[Maxn],SA[Maxn],tp[Maxn],tax[Maxn],p;

void RadixSort(void){
    for(int i=0;i<=Sz;i++)tax[i]=0;
    for(int i=1;i<=N;i++)tax[rak[i]]++;
    for(int i=1;i<=Sz;i++)tax[i]+=tax[i-1];
    for(int i=N;i;i--)SA[tax[rak[tp[i]]]--]=tp[i];
}
void SuffixSort(void){
    RadixSort();
    for(int p=0,w=1;p<N;Sz=p,w<<=1){
        p=0;
        for(int i=1;i<=w;i++)tp[++p]=N-w+i;
        for(int i=1;i<=N;i++)if(SA[i]>w)tp[++p]=SA[i]-w;
        RadixSort(),swap(rak,tp),rak[SA[1]]=p=1;
        for(int i=2;i<=N;i++)rak[SA[i]]=(tp[SA[i]]==tp[SA[i-1]]&&tp[SA[i]+w]==tp[SA[i-1]+w])?p:++p;
    }
}

int main()
{
    cin>>M;
    for(int i=1;i<=M;i++){
        cin>>s[i];
        for(int j=0;j<s[i].size();j++)rak[++N]=s[i][j]-'a'+1,tp[N]=N,P[N]=s[i][j]-'a'+1;
        rak[++N]=++Sz,tp[N]=N,P[N]=Sz;
    }
    SuffixSort();
    for(int i=1;i<=M;i++){
        int x,L=1,R=N;
        for(int j=0;j<s[i].size();j++){
            x=s[i][j]-'a'+1;
            if(L>R)continue;
            int l=L,r=R,Mid,res;
            for(;l<=r;){Mid=l+r>>1;if(P[SA[Mid]+j]< x)l=Mid+1;else r=Mid-1;}res=l,r=R,l=L;
            for(;l<=r;){Mid=l+r>>1;if(P[SA[Mid]+j]<=x)l=Mid+1;else r=Mid-1;}R=r,L=res;
        }printf("%d\n",max(0,R-L+1));
    }
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*