【NOI 2018】你的名字 / 题解

题目背景

实力强大的小A 被选为了 ION2018 的出题人，现在他需要解决题目的命名问题。

题目描述

小A 被选为了 ION2018 的出题人，他精心准备了一道质量十分高的题目，且已经把除了题目命名以外的工作都做好了。

由于 ION 已经举办了很多届，所以在题目命名上也是有规定的， ION 命题手册规定：每年由命题委员会规定一个小写字母字符串，我们称之为那一年的命名串，要求每道题的名字必须是那一年的命名串的一个非空连续子串，且不能和前一年的任何一道题目的名字相同。

由于一些特殊的原因，小A 不知道 ION2017 每道题的名字，但是他通过一些特殊手段得到了 ION2017 的命名串，现在小A 有 Q 次询问：每次给定 ION2017 的命名串和 ION2018 的命名串，求有几种题目的命名，使得这个名字一定满足命题委员会的规定，即是 ION2018 的命名串的一个非空连续子串且一定不会和 ION2017 的任何一道题目的名字相同。

由于一些特殊原因，所有询问给出的 ION2017 的命名串都是某个串的连续子串，详细可见输入格式。

输入和输出

输入格式

第一行一个字符串 S，之后询问给出的 ION2017 的命名串都是 S 的连续子串。 第二行一个正整数 Q，表示询问次数。 接下来 Q 行，每行有一个字符串 T 和两个正整数 $l,r$，表示询问如果 ION2017 的 命名串是 $S [l..r]$， ION2018 的命名串是 T 的话，有几种命名方式一定满足规定。

输出格式

输出Q 行，第 i 行一个非负整数表示第 i 个询问的答案。

样例

输入

scbamgepe
3
smape 2 7
sbape 3 8
sgepe 1 9

输出

12
10
4

数据范围和提示

思路

我们考虑求 $T$ 的一个前缀在 $S[l,r]$ 中能匹配的最长后缀。

首先我们需要对$T$和$S$分别建立 SAM，然后我们考虑对 $T$ 的一个前缀不断加入新字符。在 $S$ 的 parent 树里，如果当前状态存在一条到新插入字符的边，新状态合法，就说明新状态在 parent 树的子树中存在至少一个前缀结点，其深度在 $[l+l’,r]$ 之间。

所以我们只需要再用主席树对 DFS序 维护一下深度即可。

答案计数到 i 的时候的 $max(0,dep[i]-max(dep[fa[i]],lim))$ 也很好理解了是不是哇。

╰(￣ω￣ｏ)

代码

// name.cpp : Defines the entry point for the console application.
// XG_Zepto, 7/25/2018. All rights reserved.

#include 
#include 
#include 
#include 
#define maxn 1000005
#define mid ((l+r)>>1)
#define ll long long
using namespace std;
struct Edge {
    int to,next;
    Edge(int a=0,int b=0){
        to=a,next=b;
    }
};
struct President_Tree{
    int tree[maxn<<4],ls[maxn<<4],rs[maxn<<4],cnt; void update(int &now,int pre,int l,int r,int x){ now="++cnt;" tree[now]="tree[pre]+1;" if (l="=r)" return; (x<="mid)" rs[now]="rs[pre],update(ls[now],ls[pre],l,mid,x);" else ls[now]="ls[pre],update(rs[now],rs[pre],mid+1,r,x);" } int query(int now,int r){ (!now) return 0;>=L&&r<=r) return tree[now]; int res="0;" if (mid>=L) res+=query(ls[now],l,mid,L,R);
        if (mid>1];
    int lst,ct,nl,mp[maxn][27],fa[maxn],dep[maxn],pre[maxn],cte;
    int head[maxn],pos[maxn],root[maxn],frt[maxn],sed[maxn],dfn;
    SAMS(){lst=ct=1;}
    void add(int a,int b){
        l[++cte]=Edge(b,head[a]);
        head[a]=cte;
    }
    void expand(int i){
        int c=s[i]-'a'+1,p=ct,np=++ct;
        dep[np]=dep[lst]+1;
        pre[np]=true;
        for(p=lst;p&&!mp[p][c];p=fa[p]) mp[p][c]=np;
        if(!p){
            fa[np]=1;
            lst=np;
            return;
        }
        int q=mp[p][c];
        if(dep[q]==dep[p]+1){
            fa[np]=q;
            lst=np;
            return;
        }
        int nq=++ct;
        dep[nq]=dep[p]+1;
        fa[nq]=fa[q];
        for(int j=1;j<=26;j++) mp[nq][j]="mp[q][j];" fa[q]="fa[np]=nq;" for(;p&&mp[p][c]="=q;p=fa[p])mp[p][c]=nq;" lst="np;" } void dfs(int u){ frt[u]="++dfn;" pos[dfn]="u;" for (int i="head[u];i;i=l[i].next)" dfs(l[i].to); sed[u]="dfn;" build(){ nl="strlen(s+1);" expand(i); add(fa[i],i); dfs(1); if (pre[pos[i]]) pt.update(root[i],root[i-1],1,nl,dep[pos[i]]); else root[i]="root[i-1];" bool valid(int x,int l,int r){ return x&&pt.query(root[sed[x]],1,nl,l,r)>pt.query(root[frt[x]-1],1,nl,l,r);
    }
}S;
char t[maxn];
int lst,ct,m,mp[maxn<<1][27],fa[maxn<<1],dep[maxn<<1],pos[maxn<<1],lim[maxn<<1]; void expand(int i){ int c="t[i]-'a'+1,p=ct,ed=++ct;" dep[ed]="dep[lst]+1;" pos[ed]="i;" for(p="lst;p&&!mp[p][c];p=fa[p])" mp[p][c]="ed;" if(!p){ fa[ed]="1;" lst="ed;" return; } q="mp[p][c];" if(dep[q]="=dep[p]+1){" nq="++ct;" dep[nq]="dep[p]+1;" fa[nq]="fa[q];" pos[nq]="pos[q];" for(int j="1;j<=26;j++)" mp[nq][j]="mp[q][j];" fa[q]="fa[ed]=nq;" for(;p&&mp[p][c]="=q;p=fa[p])" main(){ scanf("%s",s.s+1); s.build(); q; scanf("%d",&q); while(q--){ l,r,nowl="0,p=1;" scanf("%s%d%d",t+1,&l,&r); m="strlen(t+1);" for (int i="1;i<=m;i++){" expand(i); while(1){ if(s.valid(s.mp[p][t[i]-'a'+1],l+nowl,r)){ nowl++; p="S.mp[p][t[i]-'a'+1];" break; if (!nowl) nowl--; (nowl="=S.dep[S.fa[p]])" lim[i]="nowl;" ll ans="0;" ans+="max(0,dep[i]-max(dep[fa[i]],lim[pos[i]]));" printf("%lld ",ans); mp[i][j]="0;" return 0; }< code>