洛谷 P4094 [HEOI2016/TJOI2016]字元串 字尾數組+二分+主席樹

題目連結

字尾數組

題目分析：

sa[i] – 第i小的字尾的編号

rank[i] --編号為i的字尾排第幾；

height[i] – 第i和第i-1的最長lcp最長公共字首；

1.二分答案，答案肯定在0—min(b-a+1, d-c+1);二分答案mid;

2.s[c–d], 滿足條件的子串一定在rank[c] 開始向前後擴充的一個區間[L, R]中，（因為和某一個串排名越接近，那麼與這個串的lcp(最長公共字首)就越大）。

3.這個區間滿足的條件就是這個區間任意一點i的height[i] >= mid; 那麼這個區間中兩兩字尾的lcp一定大于等于mid。

4如果在這個區間存在i，sa[i] 編号大于等于a,并且sa[i] + mid - 1 <= b，那麼這個mid就是可行的，可以繼續二分下去，

5，這個區間L-R使用主席樹來維持：

#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
#include<map>
using namespace std;
typedef long long lt;
 
int read()
{
    int f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}

const int maxn=100010;
int n,m,Q;
int a,b,c,d;
int rak[maxn],sa[maxn],tp[maxn],tax[maxn];
int height[maxn],mi[maxn][20];
int lft[maxn<<5],rht[maxn<<5],rt[maxn<<5],sum[maxn<<5],cnt;
char ss[maxn];

void rsort()
{
    for(int i=0;i<=m;++i) tax[i]=0;
    for(int i=1;i<=n;++i) tax[rak[i]]++;
    for(int i=1;i<=m;++i) tax[i]+=tax[i-1];
    for(int i=n;i>=1;--i) sa[tax[rak[tp[i]]]--]=tp[i];
}

void ssort()
{
    m=127;
    for(int i=1;i<=n;++i)
    rak[i]=ss[i-1],tp[i]=i;
    
    rsort(); 
    for(int k=1;k<=n;k<<=1)
    {
        int p=0;
    	for(int i=n-k+1;i<=n;++i) tp[++p]=i;
        for(int i=1;i<=n;++i) if(sa[i]>k) tp[++p]=sa[i]-k;
        
    	rsort(); 
    	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]+k]==tp[sa[i-1]+k])?p:++p;
        if(p>=n)break;
    	m=p;
    }
}

void getH()
{
    int k=0;
    for(int i=1;i<=n;++i)
    {
        if(k) k--;
        int j=sa[rak[i]-1];
        while(ss[i+k-1]==ss[j+k-1]) k++;
        height[rak[i]]=k;
    }
}

void RMQ()
{
    for(int i=1;i<=n;++i) mi[i][0]=height[i];
    for(int j=1;(1<<j)<=n;++j)
    for(int i=1;i+(1<<j)-1<=n;++i)
    mi[i][j]=min(mi[i][j-1],mi[i+(1<<j-1)][j-1]);
}

int qmin(int ll,int rr)
{
    int k=0;
    while((1<<k+1)<=rr-ll+1) k++;
    return min(mi[ll][k],mi[rr-(1<<k)+1][k]);
}

int update(int pre,int ll,int rr,int x)
{
    int tt=++cnt; sum[tt]=sum[pre]+1;
    lft[tt]=lft[pre]; rht[tt]=rht[pre];
    int mid=ll+rr>>1;
    if(ll<rr)
    {
        if(x<=mid) lft[tt]=update(lft[pre],ll,mid,x);
        else rht[tt]=update(rht[pre],mid+1,rr,x);
    }
    return tt;
}

int query(int u,int v,int ll,int rr,int s,int t)
{
    if(ll<=s&&t<=rr) return sum[v]-sum[u];
    int res=0,mid=s+t>>1;
    if(ll<=mid) res+=query(lft[u],lft[v],ll,rr,s,mid);
    if(rr>mid) res+=query(rht[u],rht[v],ll,rr,mid+1,t);
    return res;
}

int qpos1(int ll,int rr,int x)
{
    int L=ll,R=rr,res=rr;
    while(L<R){
        int mid=L+R>>1;
        if(qmin(mid+1,rr)>=x) R=mid,res=mid;
        else L=mid+1;
    }
    return res;
}

int qpos2(int ll,int rr,int x)
{
    int L=ll,R=rr,res=ll;
    while(L<R){
        int mid=L+R>>1;
        if(qmin(ll+1,mid)>=x) L=mid+1,res=mid;
        else R=mid;
    }
    return res;
}

int check(int x)
{	
    int L=qpos1(1,rak[c],x);
    int R=qpos2(rak[c],n,x);

    if(query(rt[L-1],rt[R],a,b+1-x,1,n)>0) return 1;
    else return 0;
}

int main()
{
    n=read();Q=read();
    scanf("%s",ss);
    
    ssort(); getH(); RMQ();
    for(int i=1;i<=n;++i)
    rt[i]=update(rt[i-1],1,n,sa[i]);
    
    while(Q--)
    {
    	a=read();b=read();c=read();d=read();
    	int L=1,R=min(b-a+1,d-c+1),ans=0;
    	while(L<R)
    	{
    		int mid=L+R>>1;
    		if(check(mid)) L=mid+1,ans=mid;
    		else R=mid;
        }
        if(L==R) if(check(L)) ans=L;
        printf("%d\n",ans);
    }
    return 0;
}