【题解】[NOI2018] 你的名字 后缀自动机+线段树合并 —Qiuly

$68\ pts$

比较套路的后缀自动机。

$100\ pts$

使用线段树维护节点的 $endpos$ 集合即可，由于父节点包含所有其子节点的 $endpos$ 集合，用线段树合并求父节点的 $endpos$ 集合即可。

然后在找 $1-i$ 这个前缀的最长可以匹配 $S$ 的后缀时判断一下当前所定的串是否在 $l,r$ 之间出现过即可，这个直接用线段树就好了。

Code:

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=5e5+2;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

struct Segment_tree {
    #define mid ((l+r)>>1)
    int tot,n;
    struct Node{int lc,rc;} t[N*45];
    void ins(int&x,const int l,const int r,int pos) {
        if(!x) x=++tot;if(l==r) return;
        if(pos<=mid) ins(t[x].lc,l,mid,pos);
        else ins(t[x].rc,mid+1,r,pos);
    }
    int add(int&x) {int y=++tot;ins(y,1,n,x);return y;}
    int merge(const int&x,const int&y) {
        if(!x||!y) return x|y;int now=++tot;
        t[now].lc=merge(t[x].lc,t[y].lc),t[now].rc=merge(t[x].rc,t[y].rc);
        return now;
    }
    bool query(int x,const int l,const int r,int L,int R) {
        if(!x||R<l||L>r) return false;
        if(L<=l&&r<=R) return true;
        return query(t[x].lc,l,mid,L,R)||query(t[x].rc,mid+1,r,L,R);
    }
}Tree;

struct SAM {
    char s[N];
    int last,cnt,tot;
    int ch[N<<1][26],fa[N<<1],len[N<<1],rt[N<<1],dis[N<<1];
    SAM() {cnt=last=1,tot=0;};
    inline void clear() {
        memset(fa+1,0,cnt<<2),memset(dis+1,0,cnt<<2),memset(len+1,0,cnt<<2);
        for(int i=1;i<=cnt;++i) memset(ch[i],0,26<<2);
        tot=0,cnt=last=1;
    }
    inline void ins(int c,int pos=0) {
        int p=last,np=++cnt;last=np,len[np]=len[p]+1,dis[np]=++tot;
        if(pos) rt[np]=Tree.add(pos);
        while(p&&!ch[p][c]) ch[p][c]=np,p=fa[p];
        if(!p) fa[np]=1;
        else {
            int q=ch[p][c];
            if(len[q]==len[p]+1) fa[np]=q;
            else{
                int nq=++cnt;len[nq]=len[p]+1;
                memcpy(ch[nq],ch[q],26<<2);
                fa[nq]=fa[q];fa[q]=fa[np]=nq;
                while(p&&ch[p][c]==q) ch[p][c]=nq,p=fa[p];
            }
        }return;
    }
    int t[N],a[N<<1];
    inline void pre() {
        memset(t+1,0,tot<<2);
        for(int i=1;i<=cnt;++i) t[len[i]]++;
        for(int i=1;i<=tot;++i) t[i]+=t[i-1];
        for(int i=1;i<=cnt;++i) a[t[len[i]]--]=i;
        for(int i=cnt;i>=1;--i) {
            rt[fa[a[i]]]=Tree.merge(rt[fa[a[i]]],rt[a[i]]);
        }return;
    }
    inline ll solve(int *d) {
        ll ans=0;
        memset(t+1,0,tot<<2);
        for(int i=1;i<=cnt;++i) t[len[i]]++;
        for(int i=1;i<=tot;++i) t[i]+=t[i-1];
        for(int i=1;i<=cnt;++i) a[t[len[i]]--]=i;
        for(int i=cnt;i>=1;--i) {
            int now=a[i];dis[fa[now]]=dis[now];
            ans+=max(0,len[now]-max(len[fa[now]],d[dis[now]]));
        }return ans;
    }
}S,T;

int d[N],n;
int main() {
    scanf("%s",S.s+1);
    int lens=strlen(S.s+1);
    Tree.n=lens;
    for(int i=1;i<=lens;++i) S.ins(S.s[i]-'a',i);
    S.pre(),IN(n);
    while(n--) {
        scanf("%s",T.s+1);
        int l,r,lent=strlen(T.s+1);IN(l),IN(r);
        for(int i=1,p=1,s=0;i<=lent;++i) {
            int ch=T.s[i]-'a';T.ins(ch);
            while(true) {
                if(S.ch[p][ch]&&Tree.query(S.rt[S.ch[p][ch]],1,lens,l+s,r)) {p=S.ch[p][ch],++s;break;}
                if(!s) break;--s;if(s==S.len[S.fa[p]]) p=S.fa[p];
            }d[i]=s;
        }
        printf("%lld\n",T.solve(d));T.clear();
    }
    return 0;
}