代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
#define N 1700000
#define M 100050
#define _max(x,y) ((x)>(y)?(x):(y))
#define _min(x,y) ((x)<(y)?(x):(y))
typedef long long ll;
int n,Q,r[N],ln,be[M],ed[M],m;
int wa[N],wb[N],ws[N],wv[N],sa[N],Rank[N],height[N],ql[M],qr[M],ppp[N],pos[N],lst[M];
int f[22][N],Lg[N],t[N*10],ls[N*10],rs[N*10],root[N],cnt;
inline char nc() {
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int rd() {
    int x=0; char s=nc();
    while(s<'0'||s>'9') s=nc();
    while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+s-'0',s=nc();
    return x;
}
char pbuf[100000],*pp=pbuf;
void push(const char c) {
    if(pp-pbuf==100000) fwrite(pbuf,1,100000,stdout),pp=pbuf;
    *pp++=c;
}
void write(ll x) {
    static int sta[70];
    int top=0;
    do{sta[top++]=x%10,x/=10;}while(x);
    while(top) push(sta[--top]+'0');
}
void build_suffix_array() {
    int i,j,p,*x=wa,*y=wb,*t;
    m=32;
    for(i=0;i<m;i++) ws[i]=0;
    for(i=0;i<n;i++) ws[x[i]=r[i]]++;
    for(i=1;i<m;i++) ws[i]+=ws[i-1];
    for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
    for(p=j=1;p<n;j<<=1,m=p) {
        for(p=0,i=n-j;i<n;i++) y[p++]=i;
        for(i=0;i<n;i++) if(sa[i]-j>=0) y[p++]=sa[i]-j;
        for(i=0;i<n;i++) wv[i]=x[y[i]];
        for(i=0;i<m;i++) ws[i]=0;
        for(i=0;i<n;i++) ws[wv[i]]++;
        for(i=1;i<m;i++) ws[i]+=ws[i-1];
        for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
        for(t=x,x=y,y=t,i=p=1,x[sa[0]]=0;i<n;i++) {
            if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j]) x[sa[i]]=p-1;
            else x[sa[i]]=p++;
        }
    }
    for(i=1;i<n;i++) Rank[sa[i]]=i;
    for(i=p=0;i<n-1;height[Rank[i++]]=p)
        for(p?p--:0,j=sa[Rank[i]-1];r[i+p]==r[j+p];p++);
    for(Lg[0]=-1,i=1;i<n;i++) f[0][i]=height[i],Lg[i]=Lg[i>>1]+1;
    for(i=1;(1<<i)<=n;i++) {
        for(j=1;j+(1<<i)-1<n;j++) {
            f[i][j]=min(f[i-1][j],f[i-1][j+(1<<(i-1))]);
        }
    }
}
int get_min(int x,int y) {
    int len=Lg[y-x+1],a=f[len][x],b=f[len][y-(1<<len)+1];
    return _min(a,b);
}
int lcp(int x,int y) {
    x=Rank[x],y=Rank[y];
    if(x>y) swap(x,y);
    return get_min(x+1,y);
}
void insert(int l,int r,int v,int x,int &y) {
    y=++cnt; t[y]=t[x]+1;
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(v<=mid) rs[y]=rs[x],insert(l,mid,v,ls[x],ls[y]);
    else ls[y]=ls[x],insert(mid+1,r,v,rs[x],rs[y]);
}
int Qx,Qy,ok;
void query(int l,int r,int x,int y,int qx,int qy) {
    if(t[x]==t[y]||ok) return ;
    if(l==qx&&r==qy) {ok=1; return ;}
    int mid=(l+r)>>1;
    if(qy<=mid) query(l,mid,ls[x],ls[y],qx,qy);
    else if(qx>mid) query(mid+1,r,rs[x],rs[y],qx,qy);
    else {
        query(l,mid,ls[x],ls[y],qx,mid); query(mid+1,r,rs[x],rs[y],mid+1,qy);
    }
}
int findl(int p,int len) {
    int re=p,d;
    for(d=1;p>d&&get_min(p-d+1,p)>=len;d<<=1);
    for(d>>=1;d;d>>=1) if(get_min(re-d+1,p)>=len) re-=d;
    return re;
}
int findr(int p,int len) {
    int re=p,d;
    for(d=1;p+d<n&&get_min(p+1,p+d)>=len;d<<=1);
    for(d>>=1;d;d>>=1) if(get_min(p+1,re+d)>=len) re+=d;
    return re;
}
bool check(int i,int j,int q) {
    int len=j-i+1; Qx=ql[q],Qy=qr[q];
    if(len>Qy-Qx+1) return 0;
    int p=Rank[i];
    int L=findl(p,len),R=findr(p,len);
    Qy=Qy-len+1;
    ok=0;
    query(0,ln-1,root[L-1],root[R],Qx,Qy);
    return ok;
}
int main() {
    char s=nc();
    while(s<'a'||s>'z') s=nc();
    register int i,j;
    for(;s>='a'&&s<='z';s=nc()) {
        r[ln++]=s-'a'+1;
    }
    n=ln; r[n++]=27;
    Q=rd();
    for(i=1;i<=Q;i++) {
        be[i]=n;
        s=nc();
        while(s<'a'||s>'z') s=nc();
        for(;s>='a'&&s<='z';s=nc()) {
            pos[n]=i; r[n++]=s-'a'+1;
        }
        ed[i]=n-1;
        ql[i]=rd()-1; qr[i]=rd()-1;
        if(i!=Q) r[n++]=27;
    }
    r[n++]=0;
    build_suffix_array();
    for(i=n-1;i>0;i--) {
        int p=sa[i],u=pos[p];
        if(!u) continue;
        if(lst[u]) ppp[p]=lcp(p,lst[u]);
        lst[u]=p;
    }
    for(i=1;i<n;i++) {
        int p=sa[i];
        root[i]=root[i-1];
        if(p>=0&&p<ln) insert(0,ln-1,p,root[i],root[i]);
    }
    for(i=1;i<=Q;i++) {
        ll ans=0;
        int k=be[i];
        for(j=be[i];j<=ed[i];j++) {
            if(k<j) k=j;
            while(k<=ed[i]&&check(j,k,i)) k++;
            k--;
            ans+=ed[i]-j+1-_max(k-j+1,ppp[j]);
        }
        write(ans); push('\n');
    }
    fwrite(pbuf,1,pp-pbuf,stdout);
}

评测结果