题目概述

LOJ2720

解题报告

毒瘤字符串题……这题的关键在于，给出串 $T$ ，在 $S$ 的 $[L,R]$ 子串中查询每个后缀的最长匹配前缀。

倒着考虑 $T$ 的每个后缀 $i$ ，求出在 $S$ 的 $[L,R]$ 中的最长匹配前缀长度 $len$ ，则只有 $len$ 后面的才是合法的，并且由于要去重，因此 $i$ 和之后后缀的所有LCP部分也是不用考虑的，记为 $lcp$ ，则 $i$ 的贡献就是 $|T|-i+1-\max\{len,lcp\}$ 。

$lcp=\max\{LCP(i,j)|i<j\le |T|\}$ ，这个可以通过后缀数组+set查出，主要问题就是 $len$ 怎么求。

如果没有 $[L,R]$ 的限制，则是经典问题，建出 $S$ 反串的后缀自动机，然后在 $S$ 上跑匹配就行了。

但由于限制了 $[L,R]$ ，对于当前节点 $p$ ，匹配长度 $len$ ，有可能并不能匹配成功，即匹配到的子串在 $[L,R]$ 中不存在，这个问题等价于 $p$ 节点的 $Right$ 集合中没有 $[L,R-len+1]$ 的位置，可以通过线段树合并检查出来。

由于 $len$ 的增减次数只和 $|T|$ 有关，因此在做完正常的前缀匹配流程之后，我们暴力检查当前 $p,len$ 是否可行，不可行就将 $len$ 减少一（如果 $len$ 已经不属于 $p$ 节点的长度区间，则 $p$ 也要向上跳 $fail$ ），直到可行为止。

示例程序

#include<set>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=500000,maxs=maxn<<1,maxt=4e7,maxi=26,LOG=18;

int te,n,m;char s[maxn+5],t[maxn+5];
struct SAM{
    int pl,ro,son[maxs+5][maxi],MAX[maxs+5],fai[maxs+5],pos[maxs+5];
    int newnode() {pl++;return pl;}
    SAM() {pl=0;ro=newnode();}
    int Extend(int p,int c,int id){
        int np=newnode();MAX[np]=MAX[p]+1;pos[np]=id;
        while (p && !son[p][c]) son[p][c]=np,p=fai[p];
        if (!p) {fai[np]=ro;return np;}
        int q=son[p][c];if (MAX[p]+1==MAX[q]) {fai[np]=q;return np;}
        int nq=newnode();MAX[nq]=MAX[p]+1;
        for (int i=0;i<maxi;i++) son[nq][i]=son[q][i];
        fai[nq]=fai[q];fai[q]=fai[np]=nq;
        while (p && son[p][c]==q) son[p][c]=nq,p=fai[p];
        return np;
    }
}SAM;
vector<int> e[maxs+5];
int pl,ro[maxs+5],ls[maxt+5],rs[maxt+5],sum[maxt+5];
int SA[maxn+5],rk[maxn+5],ha[maxn+5],sc[maxs+5];
int lg[maxn+5],RMQ[LOG+1][maxn+5];
set<int> S;set<int>::iterator it;
LL ans;

int newnode() {pl++;return pl;}
int Insert(int p,int pos,int l=1,int r=n){
    int now=newnode();
    ls[now]=ls[p];rs[now]=rs[p];sum[now]=sum[p]+1;
    if (l==r) return now;
    int mid=l+(r-l>>1);
    pos<=mid?ls[now]=Insert(ls[p],pos,l,mid):rs[now]=Insert(rs[p],pos,mid+1,r);
    return now;
}
int Merge(int x,int y){
    if (!x && !y) return 0;
    int now=newnode();
    if (!x || !y){
        ls[now]=ls[x+y];rs[now]=rs[x+y];sum[now]=sum[x+y];
        return now;
    }
    ls[now]=Merge(ls[x],ls[y]);
    rs[now]=Merge(rs[x],rs[y]);
    sum[now]=sum[ls[now]]+sum[rs[now]];
    return now;
}
void DFS(int x){
    if (SAM.pos[x]) ro[x]=Insert(ro[x],SAM.pos[x]);
    for (auto u:e[x]) DFS(u),ro[x]=Merge(ro[x],ro[u]);
}
void Sort(int n,int m){
    for (int i=0;i<=m;i++) ha[i]=0;for (int i=1;i<=n;i++) ha[rk[i]]++;
    for (int i=1;i<=m;i++) ha[i]+=ha[i-1];for (int i=n;i;i--) SA[ha[rk[sc[i]]]--]=sc[i];
}
void MakeSA(char *s,int n,int m=26){
    for (int i=1;i<=n;i++) rk[i]=s[i]-'a'+1,sc[i]=i,sc[i+n]=0;Sort(n,m);
    for (int k=1,p=0;p<n;m=p,k<<=1){
        p=0;for (int i=n-k+1;i<=n;i++) sc[++p]=i;
        for (int i=1;i<=n;i++) if (SA[i]>k) sc[++p]=SA[i]-k;
        Sort(n,m);for (int i=1;i<=n;i++) sc[i]=rk[i];rk[SA[1]]=p=1;
        for (int i=2;i<=n;i++)
            rk[SA[i]]=(p+=sc[SA[i-1]]!=sc[SA[i]] || sc[SA[i-1]+k]!=sc[SA[i]+k]);
    }
    for (int i=1,k=0;i<=n;i++){
        if (rk[i]==1) continue;if (k) k--;
        while (s[i+k]==s[SA[rk[i]-1]+k]) k++;
        RMQ[0][rk[i]]=k;
    }
    for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    for (int j=1;(1<<j)<n;j++)
        for (int i=2;i+(1<<j)-1<=n;i++)
            RMQ[j][i]=min(RMQ[j-1][i],RMQ[j-1][i+(1<<j-1)]);
}
int LCP(int x,int y){
    if (x>y) swap(x,y);x++;
    int k=lg[y-x+1];
    return min(RMQ[k][x],RMQ[k][y-(1<<k)+1]);
}
int Ask(int p,int L,int R,int l=1,int r=n){
    if (!p) return 0;
    if (L==l && r==R) return sum[p];
    int mid=l+(r-l>>1);
    if (R<=mid) return Ask(ls[p],L,R,l,mid); else if (L>mid) return Ask(rs[p],L,R,mid+1,r);
    else return Ask(ls[p],L,mid,l,mid)+Ask(rs[p],mid+1,R,mid+1,r);
}
int main(){
    freopen("name.in","r",stdin);freopen("name.out","w",stdout);
    scanf("%s",s+1);n=strlen(s+1);
    for (int i=n,p=SAM.ro;i;i--) p=SAM.Extend(p,s[i]-'a',i);
    for (int i=2;i<=SAM.pl;i++) e[SAM.fai[i]].push_back(i);
    DFS(SAM.ro);
    for (scanf("%d",&te);te;te--){
        int L,R;scanf("%s%d%d",t+1,&L,&R);m=strlen(t+1);
        MakeSA(t,m);S.clear();ans=0;
        for (int i=m,p=SAM.ro,len=0;i;i--){
            int lcp=0;it=S.upper_bound(rk[i]);
            if (it!=S.end()) lcp=max(lcp,LCP(rk[i],*it));
            if (it!=S.begin()) it--,lcp=max(lcp,LCP(rk[i],*it));
            S.insert(rk[i]);
            while (p && !SAM.son[p][t[i]-'a']) p=SAM.fai[p],len=SAM.MAX[p];
            if (!p) p=SAM.ro,len=0; else p=SAM.son[p][t[i]-'a'],len++;
            while (len && !Ask(ro[p],L,R-len+1)){
                len--;
                if (SAM.fai[p] && len<=SAM.MAX[SAM.fai[p]]) p=SAM.fai[p];
            }
            ans+=m-i+1-max(len,lcp);
        }
        printf("%lld\n",ans);
    }
    return 0;
}