[HEOI2016] 字符串

Description

给定一个字符串 \(S\)，有 \(m\) 个询问，每个询问给定参数 \((a,b,c,d)\) ，求 \(s[a..b]\) 的子串与 \(s[c..d]\) 的最长公共前缀长度的最大值。

Solution

读懂题意以后就很简单。把后缀数组和高度数组都搞出来，并对高度数组建立 ST 表，然后对于每个询问找到 \(s[c..d]\) 在后缀排序中的位置，二分一个 \(LCP\) 长度，检验只需要查询某一段下标区间内有没有 \(rank\) 在某个区间内的值，对 \(rank\) 数组建一个主席树即可。

我太菜了，写了一个多小时，瞎优化主席树才卡过了常。正思索着也没哪里常数太大，后来发现原来是 \(log\) 的锅……

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

int fastlog[N];

namespace st

{

int a[N][21];

void build(int *src,int n)

{

    for(int i=1; i<=n; i++)

        a[i][0]=src[i];

    for(int i=1; i<=20; i++)

        for(int j=1; j<=n-(1<<i)+1; j++)

            a[j][i]=min(a[j][i-1],a[j+(1<<(i-1))][i-1]);

}

int query(int l,int r)

{

    int j=fastlog[r-l+1];

    return min(a[l][j],a[r-(1<<j)+1][j]);

}

}

namespace sa

{

int n,m=256,sa[N],y[N],u[N],v[N],o[N],r[N],h[N],T;

// sa: Suffix Array

// r: Rank Array

// h: Height Array (between sa[i] & sa[i-1])

char str[N];

void solve()

{

    memset(sa,0,sizeof sa);

    memset(y,0,sizeof y);

    memset(u,0,sizeof u);

    memset(v,0,sizeof v);

    memset(o,0,sizeof o);

    memset(r,0,sizeof r);

    memset(h,0,sizeof h);

    n=strlen(str+1);

    for(int i=1; i<=n; i++)

        u[str[i]]++;

    for(int i=1; i<=m; i++)

        u[i]+=u[i-1];

    for(int i=n; i>=1; i--)

        sa[u[str[i]]--]=i;

    r[sa[1]]=1;

    for(int i=2; i<=n; i++)

        r[sa[i]]=r[sa[i-1]]+(str[sa[i]]!=str[sa[i-1]]);

    for(int l=1; r[sa[n]]<n; l<<=1)

    {

        memset(u,0,sizeof u);

        memset(v,0,sizeof v);

        memcpy(o,r,sizeof r);

        for(int i=1; i<=n; i++)

            u[r[i]]++, v[r[i+l]]++;

        for(int i=1; i<=n; i++)

            u[i]+=u[i-1], v[i]+=v[i-1];

        for(int i=n; i>=1; i--)

            y[v[r[i+l]]--]=i;

        for(int i=n; i>=1; i--)

            sa[u[r[y[i]]]--]=y[i];

        r[sa[1]]=1;

        for(int i=2; i<=n; i++)

            r[sa[i]]=r[sa[i-1]]+((o[sa[i]]!=o[sa[i-1]])||(o[sa[i]+l]!=o[sa[i-1]+l]));

    }

    {

        int i,j,k=0;

        for(int i=1; i<=n; h[r[i++]]=k)

            for(k?k--:0,j=sa[r[i]-1]; str[i+k]==str[j+k]; k++);

    }

}

}

namespace seg

{

int n,m,t1,t2,t3,k,a[N],b[N],c[25*N],d[25*N],e[25*N],f,g[N],q[N],s,h[N]= {1,0};

int build(int l,int r)

{

    int p=++f;

    if(r==l)

        c[p]=0;

    else

        d[p]=build(l,(l+r)/2), e[p]=build((l+r)/2+1,r);

    return p;

}

void pushup(int p)

{

    c[p]=c[d[p]]+c[e[p]];

}

int modify(int j,int l,int r,int k)

{

    int p=++f;

    c[p]=c[j];

    d[p]=d[j];

    e[p]=e[j];

    if(l==r)

    {

        c[p]++;

        return p;

    }

    if(k<=(l+r)/2)

        d[p]=modify(d[j],l,(l+r)/2,k);

    else

        e[p]=modify(e[j],(l+r)/2+1,r,k);

    pushup(p);

    return p;

}

bool query(int i,int j,int l,int r,int ql,int qr)

{

    if(l>qr||r<ql)

        return 0;

    if(l>=ql&&r<=qr)

        return (c[j]-c[i]?1:0);

    if(query(d[i],d[j],l,(l+r)/2,ql,qr)||query(e[i],e[j],(l+r)/2+1,r,ql,qr))

        return 1;

    else

        return 0;

}

bool query(int i,int j,int ql,int qr)

{

    return query(g[i-1],g[j],1,n,ql,qr);

}

void presolve(int *src,int _n)

{

    n=_n;

    g[0]=build(1,n);

    for(int i=1; i<=n; i++)

        g[i]=modify(g[i-1],1,n,src[i]);

}

}

int n,m;

int lcp(int p,int q)

{

    if(p>q)

        swap(p,q);

    if(p==q)

        return n-sa::sa[p]+1;

    else

        return st::query(p+1,q);

}

int findLeftBound(int lim,int pos,int val)

{

    int l=lim,r=pos+1;

    while(r>l)

    {

        int mid=(l+r)/2;

        if(lcp(mid,pos)>=val)

            r=mid;

        else

            l=mid+1;

    }

    if(lcp(l,pos)>=val)

        return l;

    else

        return 0;

}

int findRightBound(int lim,int pos,int val)

{

    int l=pos+1,r=lim+1;

    while(r>l)

    {

        int mid=(l+r)/2;

        if(lcp(mid,pos)>=val)

            l=mid+1;

        else

            r=mid;

    }

    if(lcp(l-1,pos)>=val)

        return l-1;

    else

        return 0;

}

int main()

{

    ios::sync_with_stdio(false);

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++) fastlog[i]=log2(i);

    scanf("%s",sa::str+1);

    sa::solve();

    st::build(sa::h,n);

    seg::presolve(sa::r,n);

    for(int i=1; i<=m; i++)

    {

        int t1,t2,t3,t4;

        scanf("%d%d%d%d",&t1,&t2,&t3,&t4);

        int l=1,r=min(t2-t1,t4-t3)+2,ax=0;

        while(r>l)

        {

            int mid=(l+r)/2;

            int lb=findLeftBound(1,sa::r[t3],mid);

            int rb=findRightBound(n,sa::r[t3],mid);

            if(seg::query(t1,t2-mid+1,lb,rb))

            {

                ax=mid;

                l=mid+1;

            }

            else

            {

                r=mid;

            }

        }

        printf("%d\n",ax);

    }

}

巴特西

[HEOI2016] 字符串 - 后缀数组,主席树,ST表,二分

[HEOI2016] 字符串

Description

Solution

Code

最新文章

热门文章