[HEOI2016/TJOI2016]字符串（后缀数组+二分+主席树/后缀自动机+倍增+线段树合并）...

news/2024/7/24 11:19:32

后缀数组解法：

先二分最长前缀长度 \(len\)，然后从 \(rnk[c]\) 向左右二分 \(l\) 和 \(r\) 使 \([l,r]\) 的 \(height\geq len\)，然后在主席树上查 \(sa[l..r]\) 是否有 \(a..b\) 中的任意一个数。时间复杂度 \(O(n\log^2 n)\)

\(Code\ Below:\)

#include <bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
int n,m,sa[maxn],tax[maxn],rnk[maxn],tp[maxn],h[maxn],f[maxn][18],g[maxn][18];
int T[maxn],L[maxn*20],R[maxn*20],sum[maxn*20],cnt;char s[maxn];

inline int read(){
    register int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return (f==1)?x:-x;
}

void SA(int m){
    int i,j,k,p,d=0;
    for(i=1;i<=n;i++) rnk[i]=s[i];
    for(i=1;i<=n;i++) tax[rnk[i]]++;
    for(i=1;i<=m;i++) tax[i]+=tax[i-1];
    for(i=n;i>=1;i--) sa[tax[rnk[i]]--]=i;
    for(k=1,p=0;p<n;m=p,k<<=1){
        p=0;
        for(i=n-k+1;i<=n;i++) tp[++p]=i;
        for(i=1;i<=n;i++) if(sa[i]>k) tp[++p]=sa[i]-k;
        for(i=1;i<=m;i++) tax[i]=0;
        for(i=1;i<=n;i++) tax[rnk[i]]++;
        for(i=1;i<=m;i++) tax[i]+=tax[i-1];
        for(i=n;i>=1;i--) sa[tax[rnk[tp[i]]]--]=tp[i];
        swap(rnk,tp);rnk[sa[1]]=p=1;
        for(i=2;i<=n;i++) rnk[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+k]==tp[sa[i]+k])?p:++p;
    }
    for(i=1;i<=n;i++) rnk[sa[i]]=i;
    for(i=1;i<=n;i++){
        p=sa[rnk[i]-1];if(d) d--;
        while(s[i+d]==s[p+d]) d++;
        h[rnk[i]]=d;
    } 
    for(i=1;i<=n;i++) f[i][0]=h[i+1],g[i][0]=h[i];
    for(j=1;j<=17;j++){
        for(i=1;i+(1<<j)-1<=n;i++) f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        for(i=(1<<j);i<=n;i++) g[i][j]=min(g[i][j-1],g[i-(1<<(j-1))][j-1]);
    }
}

void update(int &now,int pre,int l,int r,int x){
    now=++cnt;L[now]=L[pre];R[now]=R[pre];sum[now]=sum[pre]+1;
    if(l == r) return ;
    int mid=(l+r)>>1;
    if(x <= mid) update(L[now],L[pre],l,mid,x);
    else update(R[now],R[pre],mid+1,r,x);
}

int query(int u,int v,int Le,int Ri,int l,int r){
    if(Le <= l && r <= Ri) return sum[v]-sum[u];
    int mid=(l+r)>>1,ans=0;
    if(Le <= mid) ans+=query(L[u],L[v],Le,Ri,l,mid);
    if(Ri > mid) ans+=query(R[u],R[v],Le,Ri,mid+1,r);
    return ans;
}

int check(int len,int x,int a,int b){
    int l=x,r=x;
    for(int i=17;i>=0;i--)
        if(l-(1<<i)>=1&&g[l][i]>=len) l-=1<<i;
    for(int i=17;i>=0;i--)
        if(r+(1<<i)<=n&&f[r][i]>=len) r+=1<<i;
    int ans=query(T[l-1],T[r],a,b-len+1,1,n);
    return ans;
}

int main()
{
    n=read(),m=read();
    scanf("%s",s+1);SA(128);
    for(int i=1;i<=n;i++) update(T[i],T[i-1],1,n,sa[i]);
    int a,b,c,d,l,r,mid,ans=0;
    while(m--){
        a=read(),b=read(),c=read(),d=read();
        l=1;r=min(b-a+1,d-c+1);ans=0;
        while(l<=r){
            mid=(l+r)>>1;
            if(check(mid,rnk[c],a,b)) l=mid+1,ans=mid;
            else r=mid-1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

后缀自动机解法：

因为后缀自动机只能处理后缀，所以我们将原串翻转一下，将最长前缀长度转化为最长后缀长度。然后我们对原串建一个后缀自动机，二分一下最长后缀长度 \(len\)，从 \(pos[c]\) 出发倍增到 \(l[x]\geq len\) 的结点 \(x\)，然后在 \(x\) 上查询 \(endpos\) 集合是否有 \(b+len-1..a\) 的任意一个数。维护 \(endpos\) 集合可以用线段树合并。

\(Code\ Below:\)

#include <bits/stdc++.h>
using namespace std;
const int maxn=500000+10;
int n,m,a[maxn],b[maxn],last,cnt,ch[maxn][26],fa[maxn],l[maxn];
int pos[maxn],f[maxn][21],T[maxn],L[maxn*60],R[maxn*60],sum[maxn*60],tot;
char s[maxn];

inline int read(){
    register int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return (f==1)?x:-x;
}

void insert(int c){
    int p=last,q=++cnt;last=q;l[q]=l[p]+1;
    for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=q;
    if(!p) fa[q]=1;
    else {
        int r=ch[p][c];
        if(l[p]+1==l[r]) fa[q]=r;
        else {
            int s=++cnt;l[s]=l[p]+1;
            memcpy(ch[s],ch[r],sizeof(ch[r]));
            fa[s]=fa[r];fa[r]=fa[q]=s;
            for(;p&&ch[p][c]==r;p=fa[p]) ch[p][c]=s;
        }
    }
}

void pushup(int now){
    sum[now]=sum[L[now]]+sum[R[now]];
}

void update(int &now,int l,int r,int x){
    if(!now) now=++tot;
    if(l == r){sum[now]++;return ;}
    int mid=(l+r)>>1;
    if(x <= mid) update(L[now],l,mid,x);
    else update(R[now],mid+1,r,x);
    pushup(now);
}

int merge(int x,int y,int l,int r){
    if(!x||!y) return x+y;
    if(l == r){sum[x]+=sum[y];return x;}
    int mid=(l+r)>>1,z=++tot;
    L[z]=merge(L[x],L[y],l,mid);
    R[z]=merge(R[x],R[y],mid+1,r);
    pushup(z);
    return z;
}

int query(int now,int Le,int Ri,int l,int r){
    if(!now) return 0;
    if(Le <= l && r <= Ri) return sum[now];
    int mid=(l+r)>>1,ans=0;
    if(Le <= mid) ans+=query(L[now],Le,Ri,l,mid);
    if(Ri > mid) ans+=query(R[now],Le,Ri,mid+1,r);
    return ans;
}

int check(int len,int x,int L,int R){
    for(int i=20;i>=0;i--)
        if(f[x][i]&&l[f[x][i]]>=len) x=f[x][i];
    return query(T[x],L+len-1,R,1,n);
}

int main()
{
    n=read(),m=read();
    scanf("%s",s+1);last=cnt=1;
    reverse(s+1,s+n+1);
    for(int i=1;i<=n;i++){
        insert(s[i]-'a');pos[i]=last;
        update(T[pos[i]],1,n,i);
    }
    for(int i=1;i<=cnt;i++) b[l[i]]++;
    for(int i=1;i<=cnt;i++) b[i]+=b[i-1];
    for(int i=1;i<=cnt;i++) a[b[l[i]]--]=i;
    for(int i=cnt;i>=1;i--)
        if(fa[a[i]]) T[fa[a[i]]]=merge(T[fa[a[i]]],T[a[i]],1,n);
    for(int i=1;i<=cnt;i++) f[i][0]=fa[i];
    for(int j=1;j<=20;j++)
        for(int i=1;i<=cnt;i++) f[i][j]=f[f[i][j-1]][j-1];
    int a,b,c,d,l,r,mid,ans;
    while(m--){
        a=n-read()+1,b=n-read()+1,c=n-read()+1,d=n-read()+1;
        l=0,r=min(a-b+1,c-d+1),ans=0;
        while(l<=r){
            mid=(l+r)>>1;
            if(check(mid,pos[c],b,a)) l=mid+1,ans=mid;
            else r=mid-1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

转载于:https://www.cnblogs.com/owencodeisking/p/10289160.html


http://www.niftyadmin.cn/n/1253837.html

相关文章

wpa psk模式_WPA的完整形式是什么？

wpa psk模式_WPA的完整形式是什么？

wpa psk模式WPA&#xff1a;Wi-Fi保护访问 (WPA: Wi-Fi Protected Access) WPA is an abbreviation of Wi-Fi Protected Access. It is a security protocol or also known as encryption protocol which was created to take the place of the Wired Equivalent Privacy (WEP)…
阅读更多...
lcd驱动 线模式 帧模式_LCD的完整形式是什么？

lcd驱动 线模式 帧模式_LCD的完整形式是什么？

lcd驱动 线模式 帧模式LCD&#xff1a;液晶显示器 (LCD: Liquid Crystal Display) LCD is an abbreviation of "Liquid Crystal Display". LCD是“液晶显示器”的缩写。 It is a flat panel display or electronically modulated optical video display that uses t…
阅读更多...
cdp 持续数据保护_什么是CDP（哥伦比亚数据产品）？

cdp 持续数据保护_什么是CDP（哥伦比亚数据产品）？

cdp 持续数据保护CDP&#xff1a;哥伦比亚数据产品 (CDP: Columbia Data Products) CDP is an abbreviation of "Columbia Data Products". It was a data security based corporation which intended to manufacture a number of the foremost IBM PC clones in 197…
阅读更多...
blob模式识别_BLOB的完整形式是什么？

blob模式识别_BLOB的完整形式是什么？

blob模式识别BLOB&#xff1a;二进制大对象 (BLOB: Binary Large Object) BLOB is an abbreviation of Binary Large Object. It is a collection of binary data accumulated and stored in a database management system that consists of a complex data type. It reserves …
阅读更多...
[题解]洛谷P1443 马的遍历

[题解]洛谷P1443 马的遍历

原题 传送门 思路 BFS大力搜索 代码 #include<cstdio> #include<cstring> #include<queue> using namespace std;int dist[401][401],n,m,sx,sy;int nx[] {-2,-1,1,2,2,1,-1,-2},ny[] {1,2,2,1,-1,-2,-2,-1};struct Node {int x,y; };int main() {scanf(&quo…
阅读更多...
python中矩阵坐标范围_Python | 矩阵范围

python中矩阵坐标范围_Python | 矩阵范围

python中矩阵坐标范围The range of a matrix can be defined as the difference between the maximum and minimum among the elements of the matrix. In NumPy, we have provided with an inbuilt function for this operation i.e. numpy.ptp(). It returns the range of th…
阅读更多...
[转]Mybatis foreach 批量操作

[转]Mybatis foreach 批量操作

原文地址:https://blog.csdn.net/jason5186/article/details/40896043 foreach属性属性 描述item 循环体中的具体对象。支持属性的点路径访问&#xff0c;如item.age,item.info.details。具体说明&#xff1a;在list和数组中是其中的对象&#xff0c;在map中是value。该参…
阅读更多...
[大话数据结构-读书笔记] 线性表

[大话数据结构-读书笔记] 线性表

线性表 线性表是数据结构中最常用和最简单的一种结构。 1 线性表的定义 线性表&#xff0c;从名字上你就能感觉到&#xff0c;是具有像线一样的性质的表。例如一个班级的小朋友&#xff0c;一个跟着一个排着队&#xff0c;有一个打头&#xff0c;有一个收尾&#xff0c;当中的小…
阅读更多...
最新文章

Copyright @ 2022~2023