[LOJ2720][NOI2018]君の名は。

Link

Solution

首先求出TS的对应区间内每个前缀能匹配到的最长长度,用后缀自动机维护right集合比较好做。
然后将T反转求一下后缀数组,每个后缀(原串的前缀)给答案带来贡献就是n-sa[i]+1-std::max(height[i],match[sa[i]])

Code

#include <bits/stdc++.h>

template <class T>
bool Enlarge(T &a,T const &b) {
    return a<b?a=b,1:0;
}

const int XN=5e5+11;

struct SegTree {
    static int n;

    struct Node {
        Node *son[2];
        int sum;

        Node(int sum):sum(sum) {
            son[0]=son[1]=0;
        }

        void Up() {
            sum=0;
            for(int d=0;d<2;++d)
                if(son[d])
                    sum+=son[d]->sum;
        }
    }*root;

    SegTree(Node *root=0):root(root) {}

    void Add(int goal,int v) {
        std::function<void(Node*&,int,int)> Add=[&](Node *&pos,int L,int R) {
            pos=pos?new Node(*pos):new Node(0);
            if(L==R)
                pos->sum+=v;
            else {
                int M=(L+R)/2;
                goal<=M?Add(pos->son[0],L,M)
                       :Add(pos->son[1],M+1,R);     
                pos->Up();
            }
        };

        Add(root,1,n);
    }

    int Sum(int l,int r) {
        int res=0;

        std::function<void(Node*,int,int)> GetSum=[&](Node *pos,int L,int R) {
            if(!pos)
                return;
            if(l<=L && R<=r)
                res+=pos->sum;
            else {
                int M=(L+R)/2;
                if(l<=M)
                    GetSum(pos->son[0],L,M);
                if(M+1<=r)
                    GetSum(pos->son[1],M+1,R);
            }
        };

        GetSum(root,1,n);
        return res;
    }

    friend SegTree Merge(SegTree const &x,SegTree const &y) {
        std::function<Node*(Node*,Node*)> Merge=[&](Node *x,Node *y)->Node* {
            if(!x || !y)
                return x?x:y;
            else {
                Node *pos=new Node(0);
                pos->son[0]=Merge(x->son[0],y->son[0]);
                pos->son[1]=Merge(x->son[1],y->son[1]);
                pos->Up();
                return pos;
            }
        };

        return SegTree(Merge(x.root,y.root));
    }
};

int SegTree::n;

struct SuffixAutomata {
    struct Node {
        Node *son[26];
        Node *par;
        int deg,maxRight;
        SegTree T;

        Node(int maxRight=0):par(0),deg(0),maxRight(maxRight) {
            memset(son,0,sizeof(son));
        }

        void *operator new(size_t) {
            static Node *pool=(Node*)malloc(XN*2*sizeof(Node)),*mem=pool;
            nodes.push_back(mem);
            return mem++;
        }
    }*root,*last;

    static std::vector<Node*> nodes;

    std::vector<Node*> loc;

    SuffixAutomata():root(new Node),last(root) {}

    void Extend(int x) {
        Node *p=last,*nx=new Node(last->maxRight+1);
        for(;p && !p->son[x];p->son[x]=nx,p=p->par);
        if(p==0) {
            nx->par=root;
        } else {
            Node *ox=p->son[x];
            if(p->maxRight+1==ox->maxRight) {
                nx->par=ox;
            } else {
                Node *o=new Node(*ox);
                o->maxRight=p->maxRight+1;
                ox->par=nx->par=o;
                for(;p && p->son[x]==ox;p->son[x]=o,p=p->par);
            }
        }
        loc.push_back(last=nx);
    }

    void Solve() {
        SegTree::n=loc.size();
        for(size_t i=0;i<loc.size();++i)
            loc[i]->T.Add(i+1,1);
        for(auto p : nodes)
            if(p->par)
                p->par->deg++;
        std::queue<Node*> Q;
        for(auto p : nodes)
            if(!p->deg)
                Q.push(p);
        while(!Q.empty()) {
            Node *p=Q.front();Q.pop();
            if(p->par) {
                p->par->T=Merge(p->par->T,p->T);
                if(--p->par->deg==0)
                    Q.push(p->par);
            }
        }
    }

    std::vector<int> Match(int l,int r,std::string const &s) {
        Node *pos=root;
        std::vector<int> res;
        int len=0;
        for(char c : s) {
            int x=c-'a';
            while(pos!=root && !pos->son[x])
                len=(pos=pos->par)->maxRight;
            if(pos->son[x]) {
                ++len;
                pos=pos->son[x];
            }
            while(len && !pos->T.Sum(l+len-1,r))
                if(--len==pos->par->maxRight)
                    pos=pos->par;
            res.push_back(len);
        }
        return res;
    }
};

std::vector<SuffixAutomata::Node*> SuffixAutomata::nodes;

std::vector<int> SAIS(std::vector<int> &s,int sig) {
    enum Type { L,S };

    int n=s.size();
    std::vector<Type> type(n);
    std::vector<int> sa(n),cnt(sig),lp(sig),sp(sig);

    auto LMS=[&](int x) {
        return x>0 && type[x]==S && type[x-1]==L;
    };

    auto Induce=[&]() {
        for(int i=0;i<sig;++i)
            lp[i]=i?cnt[i-1]:0;
        for(int i=0;i<n;++i)
            if(sa[i]>0 && type[sa[i]-1]==L)
                sa[lp[s[sa[i]-1]]++]=sa[i]-1;
        for(int i=0;i<sig;++i)
            sp[i]=cnt[i]-1;
        for(int i=n-1;i>0;--i)
            if(sa[i]>0 && type[sa[i]-1]==S)
                sa[sp[s[sa[i]-1]]--]=sa[i]-1;
    };

    type[n-1]=S;
    for(int i=n-2;i>=0;--i)
        type[i]=s[i]<s[i+1] || (s[i]==s[i+1] && type[i+1]==S)?S:L;
    for(int x : s)
        cnt[x]++;
    for(int i=1;i<sig;++i)
        cnt[i]+=cnt[i-1];
    std::vector<int> lms;
    for(int i=0;i<n;++i)
        if(LMS(i))
            lms.push_back(i);
    for(int i=0;i<sig;++i)
        sp[i]=cnt[i]-1;
    std::fill(sa.begin(),sa.end(),-1);
    for(int i : lms)
        sa[sp[s[i]]--]=i;
    Induce();
    std::vector<int> id(n,-1);
    int c=0;
    for(int i=0,last=-1;i<n;++i)
        if(LMS(sa[i])) {
            auto Equal=[&](int x,int y)->bool {
                do if(s[x++]!=s[y++]) return 0;
                while(!LMS(x) && !LMS(y));
                return s[x]==s[y];
            };
            id[sa[i]]=last!=-1 && Equal(sa[i],last)?c-1:c++;
            last=sa[i];
        }

    std::vector<int> s1;
    for(int i=0;i<n;++i)
        if(id[i]!=-1)
            s1.push_back(id[i]);
    std::vector<int> sa1(c);
    if(c==(int)lms.size())
        for(int i=0;i<c;++i)
            sa1[s1[i]]=i;
    else
        sa1=SAIS(s1,c);
    for(int i=0;i<sig;++i)
        sp[i]=cnt[i]-1;
    std::fill(sa.begin(),sa.end(),-1);
    for(int i=lms.size()-1;i>=0;--i)
        sa[sp[s[lms[sa1[i]]]]--]=lms[sa1[i]];
    Induce();
    return sa;
}

long long Calc(std::string const &s,std::vector<int> &match) {
    int n=s.size();

    std::vector<int> a(s.size());
    for(int i=0;i<n;++i)
        a[i]=s[i]-'a'+1;
    std::reverse(a.begin(),a.end());
    match.push_back(-1);
    std::reverse(match.begin(),match.end());
    a.push_back(0);

    auto sa=SAIS(a,26+1);
    a.insert(a.begin(),-1);
    std::vector<int> rank(n+1),height(n+1);
    for(int i=1;i<=n;++i)
        rank[++sa[i]]=i;
    for(int i=1,len=0;i<=n;++i)
        if(rank[i]!=1) {
            int j=sa[rank[i]-1];
            while(a[i+len]==a[j+len]) ++len;
            height[rank[i]]=len;
            if(len) len--;
        }
    long long res=0;
    for(int i=1;i<=n;++i)
        res+=n-sa[i]+1-std::max(height[i],match[sa[i]]);

    return res;
}

int main() {
    freopen("name.in","r",stdin);
    freopen("name.out","w",stdout);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    SuffixAutomata sam;
    std::string s;
    std::cin>>s;
    for(char c : s)
        sam.Extend(c-'a');
    sam.Solve();
    int q;std::cin>>q;
    while(q--) {
        std::string t;
        int l,r;
        std::cin>>t>>l>>r;
        auto v=sam.Match(l,r,t);
        long long Ans=Calc(t,v);
        std::cout<<Ans<<'\n';
    }
    return 0;
}