回文自动机 PAM

PAM 基本内容

确定性有限状态自动机

B站视频：确定性有限状态自动机

OI-Wiki: 确定性有限状态自动机

一个确定性有限状态自动机 DFA 是一个五元组 $(Q,\Sigma,\delta,q_0,F)$ ，分别指：

1. 有限状态集合 $Q$ ：如果把一个 DFA 看成一张有向图，那么 DFA 中的状态就相当于图上的顶点。
2. 有限字符集合 $\Sigma$ ：自动机里面只有这些字符。
3. 转移函数 $\delta$ ： 定义在 $Q \times \Sigma \rightarrow Q$ 的一个函数，接受一个状态 $q \in Q$ 和一个转移字符 $c \in \Sigma $ ，结果是另一个状态 $q_1 \in Q$ 。如果把一个 DFA 看成一张有向图，那么 DFA 中的转移函数就相当于图上的边。
4. 起始状态 $q_0 \in Q$ ：自动机的初始状态。
5. 可接受状态集合 $F \subseteq Q$ ：自动机的可接受状态，也叫终止状态。

以下代码可以简单的实现一个 DFA ：

1
2
3
4
5
6
7
8
9
10
11

class DFA{
    private:
        int n;    //状态数。
        int m;    //字符集大小
        int q0;   //起始状态
        vector<vector<int>>son;  //转移函数
        vector<int>acc; //可接受状态
    public:
        DFA(){n=m=q0=0;}
        DFA(int n,int m,int q0):n(n),m(m),q0(q0){son.resize(n,vector<int>(m));}
};

回文自动机定义与构建方法

回文自动机 PAM 是用来专门处理回文串的自动机，可以在 $O(n)$ 或 $O(n\log|\Sigma|)$ 的时间内完成构建。

定义

PAM 中，起始状态 $q_0$ 为 $0$ ，但是初始时的状态却有两个，分别时 $0$ （称为偶根）和 $1$ （称为奇根）。这是因为一个回文串需要按长度的奇偶性来分类讨论。这也是与其他自动机不同的地方。

PAM 中的每个状态 $q \in Q$ 都代表一个回文串。

PAM 中可接受状态集合 $F \subseteq Q$ 为每个回文串中心（如果有）以及其右半部分。事实上，如果你不拿 PAM 去做回文多模或单模匹配，那么 $F$ 为 $Q$ 中除了 $0,1$ 的所有状态。

PAM 中的转移函数 $\delta(q \in Q,c \in \delta)$ 的结果为状态 $q$ 所代表的回文串两边都加上 $c$ 后的回文串所代表的状态。特别的， $\delta(0,c \in \Sigma)$ 代表的是回文串 $c+c$ 所对应的状态， $\delta(1,c \in \Sigma)$ 代表的是回文串 $c$ 所对应的状态。

例如当构建的字符串为 aaaba 时，自动机如下所示：

构建方法

我们采用增量法进行构建。

设第 $p$ 个字符在 PAM 上对应的节点为 $i$ ，对应的字符为 $c_p$，以第 $p$ 个字符结尾的最长回文串长度为 $len_i$ 。

假设已经构建了前 $p-1$ 个字符，现在要加入第 $p$ 个字符。设第 $p-1$ 个字符在 PAM 上对应的节点为 $q$ ，不难发现如果 $p-len_i+1$ 到 $p$ 构成回文串，那么第 $p-len_q+2$ 到 $p-1$ 也一定构成回文串。所以我们第一步可以判断当 $len_i=len_q+2$ 时，$p-len_i+1$ 到 $p$ 是否构成回文串。

此时分为两种情况：

1. $p-len_i+1$ 到 $p$ 构成回文串。此时令 $len_i=len_q+2$ 就行。
2. $p-len_i+1$ 到 $p$ 不构成回文串。此时我们发现，在只有 $len,son$ 数组的情况下，无法直接转移。此时，情况与 ACAM 中的失配相似，于是可以额外构建一个失配数组 $fail$ 。 $fail_i$ 指向 $i$ 代表的回文串的最长（回文）真后缀。那么当 $p-len_i+1$ 到 $p$ 不构成回文串时，可以再次判断当 $len_p=len_{fail_q}+2$ 时是否构成回文串，这一步可以回到步骤 1 。而 $fail$ 数组的构建可以仿照 ACAM ，设 $len_i=len_x+2$ ，则对 $fail_i$ 的构建与对 $i$ 的构建一模一样（除了对 $fail_i$ 构建时不用再处理他的 $fail$ ）。

这样，我们就完成了对 PAM 的构建。

正确性证明

从构建中不难发现，一个串 $s$ 本质不同的回文串个数为 $|s|$ ，因为 PAM 中每次操作最多增加一个点，而 PAM 中每一个点都代表一个不同的回文串。

事实上，构建 PAM 的过程中除了不断的跳 $fail$ 指针这一个操作以外，复杂度都是 $O(n)$ 或 $O(n\log|\Sigma|)$ 的。

如果把 $fail$ 指针构建成的看成一棵树，那么每一次跳 $fail$ 的最多跳该节点的深度次，并且新的 $fail$ 会让跳完后的深度增加 $1$ 。可以把这个过程简单的看为一个栈，每次会弹出 $k$ 个元素并增加一个元素。由势能分析可得复杂度不超过 $O(n)$ 或 $O(n\log|\Sigma|)$ 。

对于时间复杂度的具体分析

为什么上面会写 PAM 构建时间复杂度为 $O(n)$ 或 $O(n\log|\Sigma|)$ ？

如果字符集 $\Sigma$ 大小较小，比如只有小写字母，那么完全可以使用上面 DFA 中的模板 vector<vector<int>>son 来存储。

如果字符集 $\Sigma$ 大小较大，比如是少于 $10^9$ 的正整数，那么数组是开不下的，必须使用 C++ 中的 map 或者哈希表。而在这种情况下，哈希表速度稍慢，空间稍大，所以一般使用 map 存储，这也就是复杂度中 $O(n\log|\Sigma|)$ 来的原因。

以下是使用 int son[N][26] 来构建的 PAM 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

void init(){
    fail[0]=1;//偶根失配了就要考虑一个字符作为回文串的情况。
    len[1]=-1;//奇根是不可能失配的，所以为了不特判，可以这样设置。
}
int getfail(int x,int i){
    while(i-len[x]-1<0||c[i-len[x]-1]!=c[i])x=fail[x];
    //这里当 x=1 时， len[x]=-1, i-len[x]-1=i, c[i-len[x]-1]=c[i] ，这就是 len[1]=-1 的好处。
    return x;
}
int extend(int i,int rt){
    int x=getfail(rt,i);
    if(!son[x][c[i]-'a']){
        fail[++idx]=son[getfail(fail[x],i)][c[i]-'a'];
        son[x][c[i]-'a']=idx;
        len[idx]=len[x]+2;
    }
    return son[x][c[i]-'a'];
}

PAM 应用

本质不同回文串个数

由 PAM 定义可知 PAM 中除了 $0,1$ 节点外的每个节点都代表了原串中的一个回文串，所以原串本质不同回文串个数就是 PAM 中除去 $0,1$ 的点数，即 $idx-1$ 。

以 $i$ 结尾的回文串个数

设第 $i$ 个字符对应的 PAM 节点为 $p$ 。

不难发现， $fail_p$ 一定是前 $i-1$ 个字符中的一个回文子串，并且是 $p$ 对应的回文串的最长回文真后缀。所以以 $i$ 结尾的回文串个数应该为 $fail_p$ 的回文后缀个数再加上 $p$ 这个回文串。设 PAM 节点 $j$ 的回文后缀个数为 $cnt_j$ ，那么就有 $cnt_p=cnt_{fail_p}+1$ 。

以下代码可以构建 $cnt$ 数组：

1
2
3
4
5
6
7
8
9
10

int extend(int i,int rt){
    int x=getfail(rt,i);
    if(!son[x][c[i]-'a']){
        fail[++idx]=son[getfail(fail[x],i)][c[i]-'a'];
        son[x][c[i]-'a']=idx;
        len[idx]=len[x]+2;
        cnt[idx]=cnt[fail[idx]]+1;
    }
    return son[x][c[i]-'a'];
}

例题： 回文自动机 。

回文子串出现次数

与 AC 自动机一样，当一个回文串 $p$ 出现时，他的回文后缀都会同时出现。那么增量构建时我们只要求出新字符的最长回文子串，那么他在 $fail$ 树上的所有祖先都会同时出现。如果设 $cnt_j$ 表示 PAM 上节点 $j$ 作为某个字符的最长回文子串的次数，那么 PAM 上某个回文串 $p$ 的出现次数为他的 $fail$ 树的子树 $cnt$ 和。

以下代码可以得到 PAM 上的所有回文串的出现次数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

vector<int>v[N];
void dfs(int x){for(int u:v[x])dfs(u),cnt[x]+=cnt[u];}
int extend(int i,int rt){
    int x=getfail(rt,i);
    if(!son[x][c[i]-'a']){
        fail[++idx]=son[getfail(fail[x],i)][c[i]-'a'];
        son[x][c[i]-'a']=idx;
        len[idx]=len[x]+2;
    }
    cnt[son[x][c[i]-'a']]++;
    return son[x][c[i]-'a'];
}
void build(){
    for(int i=2;i<=idx;i++)v[fail[i]?fail[i]:1].push_back(i);
    //由于不可能有点的 fail 指向 1 ，并且 0 不太好处理，所以这里统一为 1 。
    dfs(1);
}

事实上，由于 PAM 中的 $fail$ 树一定为有序的（即 $fail_i<i$ ），所以可以直接使用下面的代码简化：

1
2
3

void build(){
    for(int i=idx;i>=2;i--)cnt[fail[i]]+=cnt[i];
}

例题： 回文串 。

两个串的最长公共回文子串

这个可以直接对两个串建立 PAM ，然后从根开始依次对比，然后求最大值就行。

同样的方法也可以求两个串有多少个回文子串相等。

以下代码可以求出两个串的最长公共回文子串：

1
2
3
4
5
6
7
8
9

void get(int p,int q){
    for(int i=0;i<26;i++)if(son[p][i]&&son[q][i]){
        res=max(res,len[p]);
        get(son[p][i],son[q][i]);
    }
}
void query_ans(){
    get(rt1_0,rt2_0);get(rt1_1,rt2_1);
}

例题： 快乐的 JYY ， 秩序魔咒 。

PAM 进阶

广义 PAM

参照广义后缀自动机，如果有多个字符串，想要求这些串的所有本质不同的回文串个数，那么就有三种方法：

1. 将所有字符串拼接起来，中间插入特殊字符，再加上一些玄学判断。
2. 将所有字符串按顺序插入到 PAM 中，每次切换字符串就重置状态为 $q_0$ 。
3. 将所有字符串插入到一个 Trie 里，然后在 Trie 上 bfs ，每次将新扩展的点在队首的状态的基础上再扩展。

这三种方法中，第一种复杂度不可靠且易错；第二种复杂度依旧线性，代码简单且在大部分题目中都正确，受到很多人的喜爱，但是根据广义 PAM 的定义（实际上没有，这个是参照广义 SAM 的），只有第三种是正确的。第二种可能在某些情况下导致复杂度错误（比如直接给一颗 Trie ，让你构建广义 PAM 或者像广义 SAM 模板一样让你输出广义 PAM 点数）。

以下代码可以构建一个广义 PAM ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

//注意，这里使用字典树而不是字符串，所以可能需要使用树上倍增之类的东西求出原来 getfail 中的 c[i-len[x]-1] 。
void insert(string &s){
    int rt=0;
    for(int i=0;i<s.size();i++){
        if(!Son[rt][s[i]-'a'])Son[rt][s[i]-'a']=++id;
        rt=Son[rt][s[i]-'a'];
    }
}
void bfs(){
    q.push(0);
    fail[0]=1;len[1]=-1;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=0;i<26;i++){
            if(Son[x][i]){
                a[Son[x][i]]=extend(i,a[x]);
                q.push(Son[x][i]);
            }
        }
    }
}

多个串的本质不同回文子串个数

建立完广义 PAM 后，直接输出 $idx-1$ 即可。

树上本质不同回文子串个数

因为树上有折的路径，所以不能用以往的方法做。

这个题目其中一个解法是点分治 + 分块 + 树状数组 + PAM 进阶结论（等差数列定理），十分麻烦。

但是在保证了树的叶子个数较少的情况下是可以使用广义 PAM 线性完成的。

有一个关于树上路径的定理：

树上的任意一跳路径均可以恰好被以树上的一个叶子节点为根时的一条从上到下的路径表示。

这里面从上到下的路径的意思是起始点为根的路径。

只要叶子数量较少，就可以使用广义 PAM ，暴力枚举叶子，然后进行 dfs 遍历得到所有路径，在 dfs 过程中可以顺便更新字典树。最后建立广义 PAM 就行了。

以下代码可以构建出 Trie ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void dfs(int x,int fa,int rt){
    if(!Son[rt][c[x]])Son[rt][c[x]]=++id;
    rt=Son[rt][c[x]];
    for(int u:v[x]){
        if(u==fa)continue;
        dfs(u,x,rt);
    }
}
void buildTrie(){
    for(int i=1;i<=n;i++){
        if(v[i].size()==1){
            dfs(i,0,0);
        }
    }
}

例题： 诸神眷顾的幻想乡 （这是广义 SAM 的题目，和这个解法一样）， 回文串 3 。

双向 PAM

原来的 PAM 仅仅只是支持后面加入字符，而双向 PAM 作为 PAM 的扩展版，可以支持从两端加入字符。

注意到 PAM 在构建时只与前一个字符有关，所以可以不对中间所有状态进行更新。

那么不妨设 $p_1$ 为开头的字符对应的 PAM 节点（这个是反着来的）， $p_2$ 为结尾的字符对应的 PAM 节点（这个是正着来的）。

由于回文串较为特殊，他的最长回文前缀和最长回文后缀一样。所以当 $p_2$ 要更新时，除非整个串变为回文串，否则 $p_1$ 是不会移动的（中间状态不管）， $p_2$ 像之前一样维护即可。同理，当 $p_1$ 要更新时，除非整个串变为回文串，否则 $p_2$ 是不会移动的（中间状态不管）， $p_1$ 像之前一样维护即可。

以下代码可以做双向插入 PAM ：

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

deque<char> s[M];
char ch;
int root_1[N],root0[N],n,i,j,fath[N],pam[N][2],tot,now1[N],now2[N],ans,len[N],fa[N],si[N],x,y,reals[N];
void insert_front(int x,int root){
	s[root].pop_front(),s[root].push_front((char)(x+'0')),s[root].push_front(' ');
	while(s[root][1]!=s[root][len[now1[root]]+2]) now1[root]=fath[now1[root]];
	if(!pam[now1[root]][x]) pam[now1[root]][x]=++tot,len[tot]=len[now1[root]]+2,reals[root]++;
	int temp = pam[now1[root]][x];
	now1[root]=fath[now1[root]];
	while(now1[root]&&s[root][1]!=s[root][len[now1[root]]+2]) now1[root]=fath[now1[root]];
	if(now1[root]) fath[temp]=pam[now1[root]][x];
	else fath[temp]=root0[root];
	now1[root]=temp;
	if(len[temp]==s[root].size()-2) now2[root]=temp;
}
void insert_back(int x,int root){
	int id = s[root].size()-1;
	s[root].pop_back(),s[root].push_back((char)(x+'0')),s[root].push_back(' ');
	while(s[root][id]!=s[root][id-len[now2[root]]-1]) now2[root]=fath[now2[root]];
	if(!pam[now2[root]][x]) pam[now2[root]][x]=++tot,len[tot]=len[now2[root]]+2,reals[root]++;
	int temp = pam[now2[root]][x];
	now2[root]=fath[now2[root]];
	while(now2[root]&&s[root][id]!=s[root][id-len[now2[root]]-1]) now2[root]=fath[now2[root]];
	if(now2[root]) fath[temp]=pam[now2[root]][x];
	else fath[temp]=root0[root];
	now2[root]=temp;
	if(len[temp]==s[root].size()-2) now1[root]=temp;
}

例题： Palindromi （启发式合并双向 PAM ，也可以用扫描线解决）。

可持久化 PAM

一般来讲，一个数据结构可持久化只需要用可持久化数组就行了。

但是那些基于势能分析的数据结构，比如并查集， KMP ……都要‘去均摊化’才能可持久化，这是因为复杂度基于势能分析，单次操作复杂度没有保证。那么可持久化后可以不断的对那个单次操作复杂度失衡的进行操作，使得复杂度错误。所以 PAM 这样一个基于栈的势能分析的数据结构，我们也要‘去均摊化’。

我们发现，在 PAM 中需要势能分析的地方时 $fail$ 数组的跳跃，所以我们要想办法降低这里的复杂度。为此，我们肯定需要一个 $qk_{i,j}$ 表示节点 $i$ 用字符 $j$ 跳 $fail$ 的结果，这样就能做到 $O(1)$ 或者 $O(\log|\Sigma|)$ 转移。而这个 $qk$ 数组每次对于新节点 $p$ ，相较于 $qk_{fail_p}$ 来说，更新的有且仅有当 $fail_p$ 作为被跳跃的第一个对象所导致的不同。所以每次可以复制 $qk$ 数组，然后只更改 $fail_p$ 带来的贡献即可。这样就成功‘去均摊化’了。

以下是一个‘去均摊化’的 PAM ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int getfail(int x,int i){
    if(i-len[x]-1<0||c[i-len[x]-1]!=c[i])return qk[x][c[i]-'a'];
    return x;
}
int extend(int i,int rt){
    int x=getfail(rt,i);
    if(!son[x][c[i]-'a']){
        fail[++idx]=son[getfail(fail[x],i)][c[i]-'a'];
        son[x][c[i]-'a']=idx;
        len[idx]=len[x]+2;
        for(int j=0;j<26;j++)qk[idx][j]=qk[fail[idx]][j];
        qk[idx][c[i-len[fail[idx]]]-'a']=fail[idx];//增加 fail[idx] 的贡献。
    }
    return son[x][c[i]-'a'];
}

至于可持久化 PAM ，只需要套用可持久化数组就行了。

双端 PAM

基于上面的可持久化 PAM 和双向 PAM ，我们容易得到一个双端 PAM （支持两头插入删除）的算法。

首先，可持久化 PAM 可以支持 PAM 单边插入删除（回退版本即可删除）。

那么套用双向 PAM 的逻辑，我们维护两头的 PAM 指针 $p_1,p_2$ ，对正着和反着的 PAM 各可持久化一遍，就可以实现一个双端 PAM 了。

使用双端 PAM 就可以轻松实现一些有关区间 PAM 之类的问题。比如区间本质不同字串个数，使用扫描线算法十分麻烦，还需要大量的回文串定理基础；但是使用双向或双端 PAM 就可以直接使用莫队或者回滚莫队解决。其余的有关区间 PAM 的算法也可以这样做。

例题： Palindromi （双端 PAM 和莫队结合）。

等差数列定理

OI-Wiki 等差数列定理 。

在面对一些需要处理以 $i$ 结尾的所有回文串时，往往难以使用树剖等算法在 $fail$ 树上直接操作，此时就要使用等差数列定理来优化了。

在得到等差数列定理之前需要一些前置引理。

引理 1

字符串 $t$ 是 $s$ 的 border ，当且仅当 $|s|-|t|$ 为 $s$ 的周期。

其中， 字符串 $t$ 是 $s$ 的 border 指 $t$ 同时为 $s$ 的前缀和后缀。$x$ 为 $s$ 的周期指对于任意的 $1 \le i \le |s|-x$ ，都有 $s_i=s_{i+x}$ 。

证明：

必要性： $t$ 是 $s$ 的 border ，所以对于任意 $1 \le i \le |t|$ ，都有 $s_i=s_{|s|-|t|+i}$ ，代入周期定义可得 $|s|-|t|$ 为 $s$ 的周期。

充分性： $|s|-|t|$ 为 $s$ 的周期，所以对于任意 $1 \le i \le |t|$ ，都有 $s_i=s_{|s|-|t|+i}$ ，代入 border 定义可得 $t$ 为 $s$ border 。

引理 2

字符串 $t$ 是回文串 $s$ 的 border ，当且仅当 $t$ 为回文串。

证明：

必要性：因为 $t$ 是 $s$ 的 border ，所以对于任意 $1 \le i \le t$ ，都有 $s_i=s_{|s|-|t|+i}$ 。又由 $s$ 为回文串得对于任意 $1 \le i \le |t|$ ，都有 $s_i=s_{|s|-i+1}$ ，所以 $s_{|s|-i+1}=s_{|s|-|t|+i}$ ，所以 $t$ 为回文串。

充分性：因为 $t$ 是回文串， $s$ 是回文串，所以 $t$ 是 $s$ 的一个回文前缀，也是一个回文后缀，所以 $t$ 是 $s$ 的 border 。

可以借助下图或 OI-Wiki 上的图理解：

引理 3

$t$ 是 $s$ 的 border 且 $2|t|>=|s|$ ，那么 $s$ 是回文串当且仅当 $t$ 是回文串。

证明：

必要性： 由引理 2 可直接推得。

充分性： 因为 $t$ 是回文串且 $t$ 是 $s$ 的 border ，那么对于任意 $1 \le i \le |t|$ 都有 $s_i=s_{|s|-|t|+i}=s_{|s|-i+1}$ ，当 $2|t|>=|s|$ 时，对于任意一个 $1 \le i \le |s|$ 都有 $s_i=s_{|s|-i+1}$ ，所以 $s$ 为回文串。

引理 4

字符串 $t$ 是回文串 $s$ 的 border ，则 $|s|-|t|$ 为 $s$ 的周期。 $|s|-|t|$ 为 $s$ 的最小周期当且仅当 $t$ 为 $s$ 的最长回文真后缀。

证明：

必要性：由引理 2 得 $t$ 是回文串且 $t$ 是 $s$ 的后缀，那么当 $|s|-|t|$ 最小时 $|t|$ 一定最大，那么必然有 $t$ 为 $s$ 的最长回文真后缀。

充分性：由引理 2 得 $t$ 是回文串且 $t$ 是 $s$ 的后缀，由引理 1 得 $|s|-|t|$ 为 $s$ 的周期。那么当 $|t|$ 最大时，即 $t$ 为 $s$ 的最长回文真后缀时， $|s|-|t|$ 取得最小值，所以 $|s|-|t|$ 为 $s$ 的最小周期。

引理 5

这是所有引理中最难理解的一个。

如果 $x,y,z$ 为回文串，且 $x$ 的最长回文真后缀为 $y$ ， $y$ 的最长回文真后缀为 $z$ ，如果令字符串 $u,v$ 满足 $x=u+y,y=v+z$ ，那么有以下 $3$ 个结论：

1. $|u| \ge |v|$ 。
2. 如果 $|u|>|v|$ ，那么 $|u|>|z|$ 。
3. 如果 $|u|=|v|$ ，那么 $u=v$ 。

证明：

首先是关于第一点的证明。由引理 4 可得 $|u|$ 为 $x$ 的最小周期， $|v|$ 为 $y$ 的最小周期。假设 $|u|<|v|$ ，由于 $y$ 为 $x$ 的后缀，所以 $u$ 是 $x$ 的周期的同时，也是 $y$ 的周期。又因为 $|v|$ 是 $y$ 的最小周期，矛盾，所以 $|u| \ge |v|$ 。

上面是 OI-Wiki 中的论述，其中 由于 y 为 x 的后缀，所以 u 是 x 的周期的同时，也是 y 的周期 论述不清楚，图也不匹配，令我想了许久才明白，这里把逻辑写明白：

当 $|u| \ge |y|$ 时，显然有 $|u| \ge |y|$ 。

当 $|u|<|y|$ 时，可以将 $y$ 平移到 $x$ 的开头（因为 $x$ 为回文串，所以可以这样干），那么 $y$ 就会完全覆盖 $u$ 。所以 $2|y| \ge |x|$ ，所以平移后的 $y$ 与原来的 $y$ 必然有交，设字符串 $t$ 使得 $y=u+t$ ，那么由于 $x$ 和 $y$ 都是回文串可得 $t$ 也是回文串，所以由引理 4 可得 $u$ 为 $y$ 的周期。

接下来证明第二点。由于 $y$ 为 $x$ 的 border ，将 $y$ 平移至开头可得 $v$ 为 $x$ 的前缀。设字符串 $w$ 满足 $x=v+w$ ，那么 $z$ 为 $w$ 的前缀，同时 $w$ 为 $x$ 的后缀， $z$ 也为 $x$ 的后缀且 $|w|>|z|$ ，所以 $z$ 为 $w$ 的 border 。假设 $|u|>|v|$ 时 $|u| \le |z|$ ，那么就有 $|z+u| \le 2|z|$ ，由 $z$ 为回文串，引理 3 可得 $w$ 为回文串，且由于 $|u|>|v|,x=u+y=v+w$ ，所以 $|w|>|y|$ 。又因为 $y$ 为 $x$ 的最长回文真后缀，矛盾，所以 $|u|>|z|$ 。

最后证明第三点。由于 $y$ 为 $x$ 的 border ，将 $y$ 平移至开头可得 $v$ 为 $x$ 的前缀。同时 $u$ 也是 $x$ 的前缀，那么由 $|u|=|v|$ 可得 $u=v$ 。

可以根据下面 OI-Wiki 中的图片进行理解：

等差数列定理

对于任意一个字符串 $s$ ，设 $s$ 的所有回文后缀的长度分别为 $l_1,l_2,\cdots l_k$ ，那么将 $l$ 从大到小排序后一定可以划分为不超过 $\log|s|$ 段等差数列，且每一段等差数列所差的字符串相等。

证明：

对于任意 $2 \le i \le k-1$ ，都有 $l_{i-1}-l_i = l_i-l_{i+1}$ 或者 $l_{i-1}-l_i \ne l_i-l_{i+1}$ 。

• 当 $l_{i-1}-l_i = l_i-l_{i+1}$ 时，由引理 5 可得所差的字符串一定相等。
• 当 $l_{i-1}-l_i \ne l_i-l_{i+1}$ 时，由引理 5 可得 $l_{i-1}-l_i > l_i-l_{i+1}$ 且 $l_{i-1}-l_i>l_{i+1}$ 。又因为 $l_{i-1}>l_i>l_{i+1}$ ，所以 $l_{i-1}>2l_{i+1}$ ，所以每次等差数列的替换都会是长度减半，所以这样的替换等差数列一定不超过 $\log|s|$ 次。

综上，对于任意一个字符串 $s$ ，那么将 $l$ 从大到小排序后一定可以划分为不超过 $\log|s|$ 段等差数列，且每一段等差数列所差的字符串相等。

在有了这个定理后，如果对于 PAM 上的某个点 $i$ ，设 $diff_i=len_i-len_{fail_i}$ ，那么对于 $fail$ 树上的所有 $i$ 的祖先 $j$ ，有 $diff_j$ 构成不超过 $\log i$ 个等差数列。我们就可以预处理出数组 $snk_i$ 表示 $i$ 在 $fail$ 树上的第一个 $j$ 满足 $diff_i \ne diff_j$ 的点。这个 $snk$ 数组的处理只需判断 $diff_i$ 与 $diff_{fail_i}$ 的关系即可。

以下代码可以处理出 $snk$ 数组：

1
2
3
4
5
6
7
8
9
10
11

int extend(int i,int rt){
    int x=getfail(rt,i);
    if(!son[x][c[i]-'a']){
        fail[++idx]=son[getfail(fail[x],i)][c[i]-'a'];
        son[x][c[i]-'a']=idx;
        len[idx]=len[x]+2;
        if(diff[idx]!=diff[fail[idx]])snk[idx]=fail[idx];
        else snk[idx]=snk[fail[idx]];
    }
    return son[x][c[i]-'a'];
}

等差数列定理的应用

等差数列定理是在当我们要对一个字符串以 $i$ 结尾的所有回文后缀进行操作时，进行优化用的。

比如如果一个题目要我们求将一个字符串 $s$ 划分为若干个回文串的方案数，我们可以设 $f_i$ 表示第 $i$ 个字符前的所有字符划分为若干个回文串的方案数，那么显然有转移方程：

$$f_i=\sum_{j=1}^i f_{j-1}[s_{j \cdots i}\text{构成回文串}]$$

初始条件为 $f_0=1$ 。

这个方程直接转移是 $O(n^2)$ ，我们要考虑优化。

由等差数列定理，所有以 $i$ 结尾的回文串长度可以构成不超过 $\log i$ 个等差数列。所以我们可以维护等差数列内的值。

设 $g_j$ 表示 PAM 上节点 $j$ 到 $fail$ 树上的节点 $snk_j$ 构成的路径的 $f$ 和。并且 $g$ 的定义范围为等差数列中长度最长的那个回文串所对应的点（相对于前 $i$ 个字符的 PAM ）。

那么对于 $f$ 的转移是十分轻松的，只需要暴力跳 $snk$ 树上的父亲即可。

至于对于 $g$ 的转移，如果对于 PAM 上节点 $j$ ， $g_j$ 的 $fail$ 树上父亲与 $snk$ 树上的父亲一样，那么 $g_j$ 只能为他自己。否则 $g_j$ 可以直接继承 $g_{fail_j}$ 在加上 $fail$ 树上 $snk_j$ 的子节点（也是 $j$ 的 $fail$ 树祖先）的 $f$ 值即可。这是因为虽然所有整体的 $f$ 值在 $fail$ 树上都会偏移 $1$ ，但是在等差数列上，原本的 $g_{fail_j}$ 所包含的 $f$ 值恰好会偏移到他的子节点（也是 $j$ 的 $fail$ 树祖先），所以只用加上新多出来的那个 $f$ 值就行。

以下代码可以求出所有的 $f$ 值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

f[0]=1;
int rt=0;
for(int i=0;i<n;i++){
    int x=getfail(rt,i);
    if(!son[x][c[i]-'a']){
        fail[++idx]=son[getfail(fail[x],i)][c[i]-'a'];
        son[x][c[i]-'a']=idx;
        len[idx]=len[x]+2;
        diff[idx]=len[idx]-len[fail[idx]];
        if(diff[idx]!=diff[fail[idx]])snk[idx]=fail[idx];
        else snk[idx]=snk[fail[idx]];
    }
    rt=son[x][c[i]-'a'];
    int t=rt;
    while(t>1){
        g[t]=f[i+1-len[snk[t]]-diff[t]];
        //snk[t] 在 fail 树上的子节点（同时也是 t 的 fail 树祖先）的 f 值。
        if(diff[t]==diff[fail[t]])(g[t]+=g[fail[t]])%=P;
        (f[i+1]+=g[t])%=P;
        t=snk[t];
    }
}

例题： 回文子串划分计数 ， Palindromic Length

PAM 高级

参考集训队 2018 年论文——《后缀树结点数》命题报告及一类区间问题的优化。

论文内容——后缀自动机在区间问题上的解法与一类区间问题的优化

集训队作业 2018 ——后缀树节点数

题目： [集训队作业2018] 后缀树节点数 。

题目内容：

给定字符串 $s$ ，询问 $m$ 次，求字符串区间 $[l,r]$ 所构成的后缀树节点个数。

满足 $m \le 3 \times 10^5,|s| \le 10^5$ 。本题中使用数字表示字符，数字范围为 $[0,n]$ 。

其中，部分测试点有特殊限制。

• 对于 $20\%$ 的数据，满足 $|s|,m \le 10^5$ 。
• 对于 $40\%$ 的数据，满足 $|s|,m \le 3 \times 10^3$ 。
• 对于 $50\%$ 的数据，满足 $|s| \times m \le 3 \times 10^8$ 。
• 对于另外 $10\%$ 的数据，满足 $s$ 为全 $0$ 字符串。
• 对于另外 $20\%$ 的数据，满足除 $|s|,m$ 外的所有数据随机生成。

特别的，此题时间限制为 $3s$ ，空间限制 $1GB$ 。

对于这个题目，首先，我们可以对于每个区间暴力构建后缀树（或称之为后缀字典树，做法是先将所有后缀插入到字典树里）。然后对于后缀树上的所有点 $i$ ，如果 $i$ 为非后缀节点且 $i$ 只有一个儿子，那么在后缀树中 $i$ 和他的儿子会合并为一个节点。直接模拟就可以做到 $O(n^2m)$ 的复杂度，可以得到 $20$ 分。

引理 1 ：一个字符串的后缀树与这个字符串的反串的后缀自动机 SAM 的 $fail$ 树等价。

证明：

设构建后缀树的字符串为 $s$ ，反串为 $t$ 。则由于 SAM 的性质， $fail$ 树上节点 $i$ 的父亲为 $i$ 所代表的字符串的最长非等价类（ $endpos$ 集合不同）后缀，那么对于 $fail$ 树上的所有叶子 $j$ ，都有 $j$ 代表的字符串为 $t$ 的前缀，也是 $s$ 的后缀。这是因为仅有 $t$ 的前缀才可能不是任何字符串的最长非等价类后缀。所以 $t$ 的 SAM 的 $fail$ 树与 $s$ 的后缀树中的叶子节点等价。由此，相同的，由于 $fail$ 的定义，可以直接得到 $s$ 的后缀树和 $t$ 的 SAM 的 $fail$ 树等价。

由这个引理，我们可以直接使用 SAM 来 $O(n\log n)$ 的建立后缀树，那么总复杂度就可以做到 $O(nm\log n)$ ，可以得到 $40$ 分。

进一步的，我们可以使用 hash 代替 C++ 中的容器 map 维护 SAM 中的子节点数组，那么单次构建复杂度只有 $O(n)$ ，总复杂度到达 $O(nm)$ ，可以得到 $50$ 分。

以上算法均为不分析的暴力算法，接下来需要分析后缀树的性质。

设 $S$ 为后缀树节点数， $s$ 为要求的串，那么由后缀树定义可知 $S$ 为所有后缀节点数加上非后缀节点且有至少两个儿子的节点数。

后缀树上任意一个节点代表的为原串中的一个子串，那么如果节点 $k$ 有至少两个不同的儿子，则至少存在两个不同的字符 $c_1,c_2$ ，使得 $k$ 代表的子串 $t$ 满足 $t+c_1$ 和 $t+c_2$ 都为 $s$ 的子串。

考虑利用这个性质。

首先，由于原问题静态且为多次询问区间问题，不好用线段树之类的数据结构直接优化，所以考虑扫描线。

当询问串从 $[l,r-1]$ 到 $[l,r]$ 时，对于串的一个后缀 $[v,r]$ ，设这个串对应子串 $t$ ，那么如果这个点产生了新的贡献，则在 $[l,r]$ 中， $t$ 必然拥有至少两个不同的后继字符，且 $t$ 在 $[l,r-1]$ 没有至少两个不同的后继字符。

这也就意味着，对于 $t$ ，设 $u$ 为其后缀树上对应的节点，至少存在他在后缀树中的两个不同的子树 $a,b$ ，满足 $a,b$ 最后出现的位置 $pos_a,pos_b$ 有 $pos_a-len_t \ge l,pos_b-len_t \ge l$ 。

如果此时我们定义一个后缀树节点的实儿子为他的所有儿子中最后访问的节点，那么不难发现，如果一个节点的实儿子没有在 $[l,r]$ 中出现过，那么其他儿子也一定不可能在 $[l,r]$ 内出现过，那么这个节点可以不考虑。否则只需要考虑该节点的虚儿子中的一个满足其在 $[l,r]$ 中出现过即可（因为已经有了一个实儿子满足条件了）。

那么，如果我能快速维护虚实儿子，就可以做到快速查询了。而这个维护虚实儿子的数据结构便是LCT。

怎么想到 LCT 的呢？怎么用 LCT 维护呢？

由后缀树的性质，如果后缀树上一个节点 $x$ 被访问，那么他在后缀树上的所有祖先都会出现过。也就是说，每次我都要对一个点所有祖先染上一个相同的新的颜色。这就很像 LCT 中的 access 操作了。

进一步的，如果把同一种颜色中的所有点看作在同一个 Splay 中，那么这个操作就和 access 一模一样了。

同时，根据 LCT 的 access 操作的均摊 $O(\log n)$ 的性质，我们会发现实儿子发生切换的次数实际上是均摊 $O(\log n)$ 次的，并且对于那些实儿子没有切换的点，说明这个点这一次出现的后继与上一次一摸一样，那么就可以只用染色，而不用去更新他。

至于每次实儿子切换时，不妨设这个点上次的颜色为 $c$ ，新的颜色为 $b$ （注意，这里的 b 不能是新染的色，不然可能就无法转移虚儿子再区间 [l,r] 中的是否出现，因为实儿子和虚儿子都需要维护，所以 b 必须是上次的值，而 c 为上上次的值），在 SAM 中的 $len$ 为 $L$ ，那么只需要将上一次的出现位置 $c$ 在树状数组上加上 $-1$ ，再给新的位置 $b-L$ （这是由于 SAM 中任意节点 $i$ 满足 $minlen_i=len_{fail_i}+1$ 的性质）在树状数组上加上 $1$ 即可。特别的，这次染新的颜色要等到 access 操作完后再进行，理由同上。

所以 LCT 就是维护这个结构的最好选择。

那么我们就可以轻松维护在后缀树中有多少个节点拥有至少两个不同的儿子了。

但是，后缀树的节点为后缀节点与非后缀节点中拥有至少两个不同的儿子的点。那么如果有一个后缀节点存在两个不同的儿子，那么我们就应该在贡献中减去他。

引理 2 ：对于后缀树中的两个后缀节点 $x,y$ ，设 $x$ 的代表串为 $y$ 的代表串的后缀。那么如果 $y$ 有两个不同的儿子，那么 $x$ 也一定有至少两个不同的儿子。

这个引理的正确性是显然的。

有了这个引理，所有后缀节点的不同儿子数量是满足单调性的，可以二分。问题就变为了快速判断一个串在区间内是否有两个不同的儿子。

有了上面的 LCT ，我们可以方便的将问题转化为快速判断一个串的虚儿子是否在区间 $[l,r]$ 内出现过。那么只需要使用哈希表将每个子串对应到后缀树上（也有可能是后缀树边上，但这样这个点就没贡献了，可以不考虑），然后判断虚儿子最后出现位置即可。

最终的答案便是 $\text{有两个儿子的后缀树节点数}+(r-l+1)-\text{有两个儿子的后缀节点数}$ 。其中的 $r-l+1$ 指的是后缀节点数。

以下代码为此题正确代码：

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

#include <bits/stdc++.h>
using namespace std;
const int N=300010;
int n,m,a[N],fail[N],len[N],pos[N],idx=1,kp[N],b[N],c[N];
//kp[x] 表示这个 SAM 点出现的位置。
//pos[x] 表示第 x 个字符对应的 SAM 点。
map<int,int>son[N];
vector<int>v[N];
void add(int x,int y){
    for(int i=x;i>=1;i-=(i&-i))
        c[i]+=y;
}
int query(int x){
    int cnt=0;
    for(int i=x;i<=n;i+=(i&-i))
        cnt+=c[i];
    return cnt;
}
int extend(int c,int rt){
    int p=rt,cur=++idx;
    len[cur]=len[rt]+1;
    while(p!=-1&&!son[p][c])son[p][c]=cur,p=fail[p];
    if(p!=-1){
        int q=son[p][c];
        if(len[p]+1==len[q])fail[cur]=q;
        else{
            int cl=++idx;
            len[cl]=len[p]+1;
            fail[cl]=fail[q];
            son[cl]=son[q];
            kp[cl]=kp[q];
            while(p!=-1&&son[p][c]==q)son[p][c]=cl,p=fail[p];
            fail[cur]=fail[q]=cl;
        }
    }
    else fail[cur]=1;
    return cur;
}
namespace LCT{
    int f[N],son[N][2],c[N],tag[N],s[N],top;
    int dir(int x){return x==son[f[x]][1];}
    int isr(int x){return x!=son[f[x]][0]&&x!=son[f[x]][1];}
    void rotate(int x){
        int y=f[x],z=f[f[x]],s=dir(x);
        if(!isr(y))son[z][dir(y)]=x;
        son[y][s]=son[x][s^1];
        if(son[x][s^1])f[son[x][s^1]]=y;
        son[x][s^1]=y;
        f[y]=x;f[x]=z;
    }
    void C(int x,int y){tag[x]=c[x]=y;}//颜色
    void down(int p){
        if(!tag[p])return ;
        C(son[p][0],tag[p]);
        C(son[p][1],tag[p]);
        tag[p]=0;
    }
    void splay(int x){
        s[top=1]=x;
        for(int y=x;!isr(y);y=f[y])s[++top]=f[y];
        while(top)down(s[top--]);
        while(!isr(x)){
            int y=f[x];
            if(!isr(y))rotate(dir(x)==dir(y)?y:x);
            rotate(x);
        }
    }
    void access(int x,int i){
        int y;
        for(y=0;x;x=f[y=x]){
            splay(x);
            if(x!=1&&c[x]&&son[x][1]){
                if(b[x])add(b[x],-1);
                b[x]=c[x]-len[x];
                add(b[x],1);
                //这里的 b 指虚儿子颜色， c 指实儿子颜色（当然也是自己的）。
                //这里由于这次 access 操作， b 将会被剔除贡献，而 c 会变为虚儿子。
            }
            son[x][1]=y;
        }
        C(y,i);
    }
}
#define P 19491001
#define ull uint64_t
namespace hashmap{
    int nxt[1048575+10],pre[1048575+10],v[1048575+10],idx;
    ull ch[1048575+10];
    void init(){memset(pre,-1,sizeof(pre));}
    void insert(ull x,int y){
        v[++idx]=y;ch[idx]=x;
        nxt[idx]=pre[x&1048575],pre[x&1048575]=idx;
    }
    int get(ull x){
        for(int i=pre[x&1048575];i!=-1;i=nxt[i]){
            if(ch[i]==x)return v[i];
        }
        return 0;
    }
}
ull p[N],h[N];
void hashe(int *c,int n){
    p[0]=1;
    for(int i=1;i<=n;i++){
        h[i]=h[i-1]*P+c[i];
        p[i]=p[i-1]*P;
    }
}
ull get(int l,int r){return h[r]-h[l-1]*p[r-l+1];}
void dfs(int x){
    if(x!=1){
        int r=kp[x],l=kp[x]-len[x]+1;//计算这个子串的哈希值。
        hashmap::insert(get(l,r),x);
    }
    for(int u:v[x])dfs(u);
}
int ans[N];
struct node{int l,id;};
vector<node>V[N];
int main(){
    hashmap::init();
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[n-i+1],a[n-i+1]++;//要建立反串， a[n-i+1]++ 是为了防止 0 。
    fail[1]=-1;
    int rt=1;
    for(int i=1;i<=n;i++)rt=extend(a[i],rt),kp[rt]=i,pos[i]=rt;
    for(int i=1;i<=idx;i++){
        if(fail[i]>0){
            v[fail[i]].push_back(i);
            LCT::f[i]=fail[i];
            //LCT 维护的是反串 SAM ，即后缀树。
        }
    }
    hashe(a,n);
    dfs(1);
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        V[n-l+1].push_back({n-r+1,i});
    }
    for(int i=1;i<=n;i++){
        LCT::access(pos[i],i);
        for(node j:V[i]){
            ans[j.id]=query(j.l)+i-j.l+1;
            int l=j.l,r=i-1,p=0;
            while(l<=r){
                int mid=(l+r)>>1;
                int t=hashmap::get(get(j.l,mid));
                if(!t||b[t]+len[t]<=mid)r=mid-1;
                else p=mid-j.l+1,l=mid+1;
                //如果找不到说明是后缀树上节点，可以忽略。
            }
            ans[j.id]-=p;
        }
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
    return 0;
}

类比训练——区间本质不同字串个数

题目： 区间本质不同子串个数 。

题目内容：

给定一个只有小写字母的字符串 $s$ ，询问 $m$ 次，每次询问 $s$ 的一个子串 $[l,r]$ 的本质不同字串个数。

满足 $|s| \le 10^5,m \le 2 \times 10^5,1 \le l \le r \le |s|$ 。

时间限制 $1s$ ，空间限制 $512 MB$ 。

对于这个题目，由于题目多次询问区间，原串静态，一般如树链剖分等数据结构无法较好的维护，于是可以像上一题一样，使用扫描线，对所有询问右端点排序。

面对这种本质不同的问题，我们一般是维护所有子串的最后出现的位置。

考虑建立 SAM ，那么对于任意一个 SAM 上的节点 $x$ ，如果他代表的子串 $t$ 出现过，那么 $x$ 在 $fail$ 树上的所有节点都会同时出现。如此，我们考虑 LCT 进行维护。

怎么想到 LCT 的呢？怎么用 LCT 维护呢？

如果我们对所有串的右端点最后出现的位置打标记，比如说 SAM 上节点 $i$ 表达的子串 $T$ 最后出现的右端点位置为 $c_i$ ，那么当查询区间为 $[l,r]$ （当前扫描线扫到 $r$ ）时，这个子串会对所有 $l \in [1,c_i-|T|+1]$ 贡献。

不难发现，打标记这个操作和上一题中的给祖先染色的操作一模一样，所以我们也可以用 LCT 维护他，使用 access 操作进行打标记操作。

那么我们在打标记时，如果这个点上一次染的色为 $b$ ，新颜色为 $B$ ，目前整个 splay 所代表的子串最短为 $ml$ ，最长为 $l$ ，那么上一次这个子串得贡献（即出现位置）为区间 $[b-l+1,b-ml+1]$ （由于 SAM 的性质，这个一定是连续区间）。我们只需要撤销这个标记即可。

最后，对于整棵 access 后的 splay ，我们给整个 splay 下一个染色标记 $B$ ，然后再对区间 $[B-l+1,B-ml+1]$ 进行区间 $+1$ 操作就行了（或者说直接用区间 $[B-l+1,B]$ 也行，因为最小的字串长度必然是 $1$ ）。

所以 LCT 是维护这个结构的最好选择。

到此，这个题目就结束了。如果使用线段树维护贡献，那么每次只需要查询区间 $[l,r]$ 内的贡献和就行了。

以下代码为此题正确代码：

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=400010;
char c[N];
int n,idx=1,fail[N],pos[N],len[N],son[N][26],m,ans[N],num[N],tag[N];
int extend(int c,int rt){
    int p=rt,cur=++idx;
    len[cur]=len[p]+1;
    while(p!=-1&&!son[p][c])son[p][c]=cur,p=fail[p];
    if(p!=-1){
        int q=son[p][c];
        if(len[p]+1==len[q])fail[cur]=q;
        else{
            int cl=++idx;
            len[cl]=len[p]+1;
            fail[cl]=fail[q];
            memcpy(son[cl],son[q],sizeof(son[q]));
            while(p!=-1&&son[p][c]==q)son[p][c]=cl,p=fail[p];
            fail[q]=fail[cur]=cl;
        }
    }
    else fail[cur]=1;
    return cur;
}
void push(int p,int x,int l,int r){tag[p]+=x;num[p]+=x*(r-l+1);}
void down(int p,int l,int r){
    if(!tag[p])return ;
    int mid=(l+r)>>1;
    push(p<<1,tag[p],l,mid);
    push(p<<1|1,tag[p],mid+1,r);
    tag[p]=0;
}
void add(int p,int l,int r,int ql,int qr,int x){
    if(ql<=l&&r<=qr){
        push(p,x,l,r);
        return ;
    }
    int mid=(l+r)>>1;
    down(p,l,r);
    if(mid>=ql)add(p<<1,l,mid,ql,qr,x);
    if(mid<qr)add(p<<1|1,mid+1,r,ql,qr,x);
    num[p]=num[p<<1]+num[p<<1|1];
}
int query(int p,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)return num[p];
    int mid=(l+r)>>1,res=0;
    down(p,l,r);
    if(mid>=ql)res+=query(p<<1,l,mid,ql,qr);
    if(mid<qr)res+=query(p<<1|1,mid+1,r,ql,qr);
    return res;
}
struct LCT{
    int f[N],son[N][2],c[N],tag[N],s[N],top,ln[N],val[N];
    //ln[p] 表示 SAM 节点 p 所代表的最短字串长度。
    //val[p] 表示 splay 上的以我为根的子树内最小的 ln 值。
    //这里由于一个节点代表的最长子串长度已经在 SAM 上维护好了，所以不用维护。
    void up(int p){
        val[p]=ln[p];
        if(son[p][0])val[p]=min(val[p],val[son[p][0]]);
        if(son[p][1])val[p]=min(val[p],val[son[p][1]]);
    }
    int dir(int x){return x==son[f[x]][1];}
    int isr(int x){return x!=son[f[x]][0]&&x!=son[f[x]][1];}
    void rotate(int x){
        int y=f[x],z=f[f[x]],s=dir(x);
        if(!isr(y))son[z][dir(y)]=x;
        son[y][s]=son[x][s^1];
        if(son[x][s^1])f[son[x][s^1]]=y;
        son[x][s^1]=y;
        f[y]=x;f[x]=z;
        up(y);up(x);
    }
    void C(int x,int y){tag[x]=c[x]=y;}
    void down(int p){
        if(!tag[p])return ;
        if(son[p][0])C(son[p][0],tag[p]);
        if(son[p][1])C(son[p][1],tag[p]);
        tag[p]=0;
    }
    void splay(int x){
        s[top=1]=x;
        for(int y=x;!isr(y);y=f[y])s[++top]=f[y];
        while(top)down(s[top--]);
        while(!isr(x)){
            int y=f[x];
            if(!isr(y))rotate(dir(x)==dir(y)?y:x);
            rotate(x);
        }
    }
    void access(int x,int i){
        int t=x;
        for(int y=0;x;x=f[y=x]){
            splay(x);son[x][1]=y;up(x);
            if(c[x])add(1,1,n,c[x]-len[x]+1,c[x]-val[x]+1,-1);
        }
        splay(t);C(t,i);add(1,1,n,i-len[t]+1,i,1);
    }
};
LCT t{};
struct node{
    int l,id;
};vector<node>V[N];
signed main(){
    cin>>(c+1)>>m;
    n=strlen(c+1);
    int rt=1;
    fail[1]=-1;
    for(int i=1;i<=n;i++)rt=extend(c[i]-'a',rt),pos[i]=rt;
    for(int i=2;i<=idx;i++){
        t.f[i]=fail[i];
        t.ln[i]=t.val[i]=len[fail[i]]+1;// SAM 的性质： minlen[x]=len[fail[x]]+1 。
    }
    t.ln[1]=t.val[1]=1;//特别处理，防止溢出。
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        V[r].push_back({l,i});
    }
    for(int i=1;i<=n;i++){
        t.access(pos[i],i);
        for(node j:V[i]){
            ans[j.id]=query(1,1,n,j.l,i);
        }
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
    return 0;
}