【NOI 2018】你的名字 / 题解

【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

数据范围和提示

测试点 $∣S∣≤$ $Q≤$ $∑∣T∣≤$ 其他限制
1 $200$ $200$ $40000$ $∣T∣≤200$
2 $1000$ $200$ $40000$ $∣T∣≤200$
3 $1000$ $200$ $40000$ $∣T∣≤200$
4 $1000$ $200$ $5×10^5$
5 $1000$ $200$ $5×10^5$
6 $5×10^5$ $1$ $5×10^5$
7 $5×10^5$ $1$ $5×10^5$
8 $10^5$ $10^5$ $2×10^5$
9 $10^5$ $10^5$ $2×10^5$ 字符串随机
10 $2×10^5$ $10^5$ $4×10^5$
11 $2×10^5$ $10^5$ $4×10^5$ 字符串随机
12 $3×10^5$ $10^5$ $6×10^5$
13 $3×10^5$ $10^5$ $6×10^5$ 字符串随机
14 $4×10^5$ $10^5$ $8×10^5$
15 $4×10^5$ $10^5$ $8×10^5$ 字符串随机
16 $5×10^5$ $10^5$ $10^6$
17 $5×10^5$ $10^5$ $10^6$ 字符串随机
18 $2×10^5$ $10^5$ $10^6$
19 $3×10^5$ $10^5$ $10^6$
20 $4×10^5$ $10^5$ $10^6$
21 $5×10^5$ $10^5$ $10^6$
22 $5×10^5$ $10^5$ $10^6$
23 $5×10^5$ $10^5$ $10^6$
24 $5×10^5$ $10^5$ $10^6$
25 $5×10^5$ $10^5$ $10^6$

思路

我们考虑求 $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))$ 也很好理解了是不是哇。

╰( ̄ω ̄o)

代码

// 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;
        if (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 l,int r,int L,int R){
        if (!now) return 0;
        if (l>=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;
    }
    void build(){
        nl=strlen(s+1);
        for (int i=1;i<=nl;i++) expand(i);
        for (int i=2;i<=ct;i++) add(fa[i],i);
        dfs(1);
        for (int i=1;i<=dfn;i++){
            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;
    }
    int q=mp[p][c];
    if(dep[q]==dep[p]+1){
        fa[ed]=q;
        lst=ed;
        return;
    }
    int 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]) mp[p][c]=nq;
    lst=ed;
}
int main(){
    scanf("%s",S.s+1);
    S.build();
    int Q;
    scanf("%d",&Q);
    while(Q--){
        int l,r,nowl=0,p=1;
        scanf("%s%d%d",t+1,&l,&r);
        m=strlen(t+1);
        lst=ct=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) break;
                nowl--;
                if (nowl==S.dep[S.fa[p]]) p=S.fa[p];
            }
            lim[i]=nowl;
        }
        ll ans=0;
        for (int i=2;i<=ct;i++)
            ans+=max(0,dep[i]-max(dep[fa[i]],lim[pos[i]]));
        printf("%lld
",ans);
        for (int i=1;i<=ct;i++)
            for (int j=1;j<=26;j++)
                mp[i][j]=0;
    }
    return 0;
}
Show Comments