P4770 [NOI2018] 你的名字 洛谷黑题题解详解

[NOI2018] 你的名字

题目背景

实力强大的小 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\dots r}$，ION2018 的命名串是 $T$ 的话，有几种命名方式一定满足规定。

输出格式

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

样例 #1

样例输入 #1

scbamgepe
3
smape 2 7
sbape 3 8
sgepe 1 9
1
2
3
4
5

样例输出 #1

12
10
4
1
2
3

提示

更多样例

更多样例请在附加文件中下载。

样例 2

见附加文件中的 name2.in 与 name2.ans。

数据范围

对于前 $17$ 个测试点的所有询问有 $l=1,r=|S|$。

对于所有数据，保证 $1\le l\le r\le |S|$,$1\le |T|\le 5\times 10^5$

感谢 @Wen_kr 提供的一组 hack 数据。

显然这种后缀自动机duliu题几句话是说不清的……

所以我们还是来慢慢分析这题的性质好了

前置芝士:后缀自动机(sam)
蛤？做noi的字符串题不会sam,建议出门左转你站模板区学习一下

前置芝士:线段树合并
很多题目都是后缀自动机和线段树合并套在一起进行的，这是因为线段树合并这个算法可以很方便的维护后缀自动机的right集合，如果你不会线段树合并的话，可以翻一翻往期的咕咕日报，有非常详细的讲解

不过值得注意的是这道题用的线段树合并和大家惯用的合并写法不是很一致，后面会具体讲这部分内容

本题题解
先来重新描述一下模糊不清的题意

给定一个模板串SS,多组询问,每次给出一个询问字符串TT和一个区间(l,r)(l,r)

要求你输出TT有多少个本质不同的子串,满足这个子串没有在S的(l,r)(l,r)这段区间当中出现

然后我们接着转化一波就是询问你有几个T的本质不同的子串满足这个子串在SS的给定区间当中出现了，然后我们求出这个东西之后拿T的所有本质不同子串去减就能得到答案了(如果连求T本质不同子串数目这点都不会的建议重新学一遍sam)

对于这题来讲我们先来考虑几个比较特殊的部分分再来解决最后的问题会比较有效，所以让我们一个部分分一个部分分的解决这题

Case1:l=1,r=|S|l=1,r=∣S∣
这样的话我们可以先对字符串SS建一个后缀自动机然后对询问串TT建一个后缀自动机，由于TT的总长不是特别长因此我们的复杂度是对的

接下来为了做这道题我们需要知道一个知识，就是给定一个模板串SS和一个匹配串TT，现在我们希望对于TT的每一个前缀(1,i)(1,i)求出一个最长的字符串P，满足P是(1,i)(1,i)的后缀并且PP是S的子串

通俗点说就是把TT放到SS上去跑匹配

那么其实这个东西也十分的简单，我们仔细观察一下parent树的性质就会发现parent树的性质和ac自动机的fail树性质相当的像，甚至我们可以说sam其实就是把一个字符串的所有子串抽出来建了一个ac自动机

那么我们向前添加一个字符的时候只需要看sam上对应的节点有没有对应的出边:

如果有对应的出边我们直接走上去并且让匹配长度+1,

否则我们不停的跳parent树直到parent树上一个节点有对应的出边为止，此时我们把匹配长度更新为parent树上节点len值+1。

如果跳到了根依然失配那么我们将匹配长度更新为0

这样我们就求出了TT的每一个前缀的匹配长度了

那么我们有了这个匹配长度之后有什么用呢？

我们在T的后缀自动姬的每一个节点上维护一个ans值表示这个节点的最长合法长度,

解释一下ans的含义就是这样

我们知道给定一个后缀自动机节点再给定一个字符串长度可以唯一确定一种本质不同子串,那么一个节点的ans值就表示所有长度小于ans并且也被这个节点表示的字符串都是S的子串

我们在S的后缀自动机上跑匹配的同时我们也在T的后缀自动机上跑T这个串,并且每次匹配串的长度减小的时候我们在T的parent树上跳直到这个节点的len值变的合法,然后用当前匹配的长度去更新这个点到根路径上节点的ans值

显然暴力跳链复杂度是假的，但是我们发现当一个点的ans值等于len值的时候这个节点的祖先的ans值也全部等于len值，因此我们暴力跳链如果这个点的ans值等于len我们就停止跳链，这样复杂度就真了

最后的答案就是所有点ans值-父亲的len值之和了，当然由于我们做了个补集转化还要用本质不同的子串数目减去我们求出的数才能输出

Case2:l,r任意
我们发现其实我们只要知道(l,r)(l,r)这段区间的后缀自动机长什么样就可以直接执行上面的算法了，但是问题是我们没有办法轻松的得知一个区间的后缀自动机

但是仔细想想我们上面算法流程真的需要后缀自动机本身吗？

其实并不是，我们只是借助S的后缀自动机求出了T的每个前缀的匹配长度

我们在L=1,r=|S|L=1,r=∣S∣所用的算法仅仅对S的后缀自动机执行了这样几个操作

1.检查S的一个节点是否有某一个字符的出边，如果有那就转移上去

2.跳parent树

3.读取一个节点的len值

换句话说我们如果能够实现上面几个操作，并且保证我们读取的len值是这个节点在以(l,r)(l,r)这个区间为模板串意义下的len,转移到的节点也是这个节点在(l,r)(l,r)意义下的出边，我们的算法就还是对的

现在我们来考虑如何实现这几个操作

我们使用线段树合并来维护每一个后缀自动机节点的right集合，线段上维护的是区间最大值

当我们判断是否存在一条在(l,r)(l,r)意义下指向p的转移边的时候，我们只需要查找节点p的righ集合在(1,r)(1,r)的区间最大值然后和l进行比较如果这个最大值比ll小就证明这个转移边在(l,r)(l,r)作为模板串的时候并不合法，不能进行转移

同样的，当我们读取一个节点的len值的时候我们还是找出(1,r)(1,r)的区间最大值,在(l,r)(l,r)作为模板串的意义下，这个节点的len值应该是\min(len,l-maxpos(1,r)+1)min(len,l−maxpos(1,r)+1)

至于跳parent树的过程，我们仔细研究一下parent树的定义就会发现其实在整个大的后缀自动机上跳就肥肠符合我们的需要了，所以跳原来后缀自动机上的parent树即可

然后我们发现这里的线段树合并和我们平常写的可能不是很一样，平常我们合并两个线段树的时候是将某一个线段树插入到另一个线段树里，然后我们一般的套路是一边在树上dfs一边合并线段树，然后当我们dfs到节点u的时候我们就get到u子树中的信息

那么我们会发现当我们按照平常的线段树合并算法合并两个线段树u和v的时候原来的两个线段树都会被销毁

您可能一开始像我一样naive的认为我们在线段树合并的时候是把u的一些孩子指针指向了v线段树，所以被销毁的只有u线段树而没有v线段树

然鹅这种想法是相当错误的，当我们合并了u和v之后v的一些节点就成为了u线段的一部分，如果此时我们把u和另外一个线段树v’合并,那么同时属于u和v的线段树节点就会被修改，此时v就相当于被销毁了

为了避免这种尴尬的情况发生(显然如果出现这个bug你会看着线段树合并的代码挠半天头而依然不知所措，并且小数据你有很大的概率wa不了)我们需要将线段树合并的过程可持久化

具体来讲每次我们需要修改u节点的孩子指针的时候我们新开一个节点然后把这个节点的孩子指针指向合并左子树和右子树产生的节点，这样我们就保留了每一个版本的线段树，此时我们就可以读取任意一个节点的right集合了~

代码的话不是很好写，细节也比较多，请注意封装和细节的分类讨论

上代码~

#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e6+10;typedef long long ll;char mde[N];int n;int nl;int nr;int m;
struct suffixautomaton//简易后缀自动机板子 
{
    int mp[N][27];int ct;int fa[N];int len[N];int n;
    inline int& operator [](const int& x){return len[x];}
    inline void ih(int x){n=x;for(int i=1;i<=n;i++)len[i]=i;ct=n+1;}
    inline void clr()
    {
        for(int i=1;i<=ct;i++)for(int j=1;j<=26;j++)mp[i][j]=0;
        for(int i=1;i<=ct;i++)fa[i]=0;for(int i=1;i<=ct;i++)len[i]=0;
    }
    inline void ins(int x,int c)
    {
        int p=(x==1)?n+1:x-1;for(;p&&mp[p][c]==0;p=fa[p])mp[p][c]=x;
        if(p==0){fa[x]=n+1;return;}int q=mp[p][c];
        if(len[q]==len[p]+1){fa[x]=q;return;}len[++ct]=len[p]+1;
        for(int i=1;i<=26;i++)mp[ct][i]=mp[q][i];
        for(;p&&mp[p][c]==q;p=fa[p])mp[p][c]=ct;fa[ct]=fa[q];fa[q]=fa[x]=ct;
    }
};
namespace SM
{
    suffixautomaton sam;int s[40*N][2];int va[40*N];int cnt;
    int v[N];int x[N];int al[N];int ct;
    inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
    # define mov(p,c) (p=sam.mp[p][c])
    # define jup(p) (p=sam.fa[p])
    inline void ins(int p,int l,int r,int pos) 
    {
        va[p]=pos;if(r-l==1){return;}int mid=(l+r)/2;
        if(pos<=mid)ins(s[p][0]=++cnt,l,mid,pos);else ins(s[p][1]=++cnt,mid,r,pos);
    }
    inline int mg(int p1,int p2,int isr)//这里的合并是可持久化的，不会销毁任意一颗线段树 
    {
        int nw=(isr)?p1:++cnt;
        if(s[p1][0]&&s[p2][0])s[nw][0]=mg(s[p1][0],s[p2][0],0);
            else s[nw][0]=(s[p2][0])?s[p2][0]:s[p1][0];
        if(s[p1][1]&&s[p2][1])s[nw][1]=mg(s[p1][1],s[p2][1],0);
            else s[nw][1]=(s[p2][1])?s[p2][1]:s[p1][1];
        va[nw]=max(va[s[nw][0]],va[s[nw][1]]);return nw;
    }
    inline int qry(int p,int l,int r,int dl,int dr)//查询区间最大值 
    {
        if((p==0)||(dl==l&&r==dr))return va[p];int mid=(l+r)/2;int res=0;
        if(dl<mid)res=max(res,qry(s[p][0],l,mid,dl,min(dr,mid)));
        if(mid<dr)res=max(res,qry(s[p][1],mid,r,max(dl,mid),dr));
        return res;
    }
    inline void dfs(int u){for(int i=al[u];i;i=x[i])dfs(v[i]),mg(u,v[i],1);}
    inline void build()
    {
        sam.ih(n);for(int i=1;i<=n;i++)sam.ins(i,mde[i]-'a'+1);
        cnt=sam.ct;for(int i=1;i<=sam.ct;i++)add(sam.fa[i],i);
        for(int i=1;i<=n;i++)ins(i,0,n,i);dfs(n+1);
    }
    inline void trs(int& p,const int& c,int& len)//暴力跳fail树进行转移 
    {
        for(;p!=n+1;jup(p),len=sam[p])
            if(sam.mp[p][c])
            {
                int mle=qry(sam.mp[p][c],0,n,0,nr)-nl+1;
                if(sam[sam.fa[p]]<mle){len=min(len+1,mle);mov(p,c);return;}
            }
        if(p==n+1&&(sam.mp[p][c]==0||qry(sam.mp[p][c],0,n,0,nr)<nl)){len=0;return;}
        mov(p,c);len++;
    }
    # undef mov
    # undef jup
}
namespace SM2
{
    suffixautomaton sam;char mde[N];int le;
    int v[N];int x[N];int al[N];int ct;int mx[N];
    inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
    # define mov(p,c) (p=sam.mp[p][c])
    # define jup(p) (p=sam.fa[p])
    inline void build()
    {
        for(int i=1;i<=sam.ct;i++)al[i]=0;ct=0;sam.clr();scanf("%s",mde+1);
        scanf("%d%d",&nl,&nr);le=1;for(;mde[le+1]!='\0';le++);sam.ih(le);
        for(int i=1;i<=le;i++)sam.ins(i,mde[i]-'a'+1);
        for(int i=1;i<=sam.ct;i++)add(sam.fa[i],i),mx[i]=sam[sam.fa[i]];
    }
    inline void aju(int p,const int& lim)//打标记 
    {
        for(;p!=le+1&&sam[sam.fa[p]]>=lim;jup(p));
        for(;p!=le+1&&sam[p]>mx[p];jup(p))mx[p]=max(mx[p],min(sam[p],lim));
    }
    inline ll dfs(int u)
    {ll ret=0;for(int i=al[u];i;i=x[i])ret+=mx[v[i]]-sam[u]+dfs(v[i]);return ret;}
    inline ll dfs2(int u)
    {ll ret=0;for(int i=al[u];i;i=x[i])ret+=sam[v[i]]-sam[u]+dfs2(v[i]);return ret;}
    inline void solve(int z)
    {
        for(int i=1,p1=n+1,p2=le+1,nle=0;i<=le;i++)
            mov(p2,mde[i]-'a'+1),SM::trs(p1,mde[i]-'a'+1,nle),aju(p2,nle);
        printf("%lld\n",dfs2(le+1)-dfs(le+1));
    }
    # undef mov
    # undef jup
}
int main()
{
    scanf("%s",mde+1);for(n=1;mde[n+1]!='\0';n++);SM::build();scanf("%d",&m);
    for(int i=1;i<=m;i++)SM2::build(),SM2::solve(i);return 0;//拜拜程序~ 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108