字符串学习笔记

涉及了 Trie树，KMP算法，AC自动机，SA 等字符串全家桶的内容。

〇. 字符串哈希

在任何场面中都十分有用的 hash 值，如果想利用其表示某个串的前缀，可以类比秦九昭算法弄成多项式的形式：

H(1) = s_1,~H(i) = H(i-1)*seed+s_i

那么对于任意一个子串 $S[l,r]$ ，我们可以在这样表示：

H(l,r) = H(r)-H(l-1)*seed^{~r-l+1}

比方说求 i 和 j 的 LCP，只需要二分枚举长度 len，判断 $H(i,len)$ 是否和 $H(j,len)$ 相同就行了。

壹. Trie树

1. 普通 Trie 树

大家都会。

2. 可持久化 Trie 树

会持久化线段树了就会。

贰. 前缀函数及 KMP 算法

1. 解决对象

在 $O(n)$ 时间内快速解决单模式串的匹配问题。

2. 前缀函数

定义 $nex_i$ 数组为子串 $s_{0\to i}$ 最长的相等的真前缀与真后缀的长度。

知道了各前缀函数值，我们在进行模式串失配的时候就可迅速回到上一个匹配点，对总匹配过程进行加速。

求前缀函数的过程与 KMP 本质上没有区别，其核心是两个性质（默认数组下标从 0 开始）：

已知 $nex_i$ ，则对于 $nex_{~i+1}$ ，其贡献不会超过 1.
若第 k 长相同前缀长度为 j ，则第 k+1 长相同前缀长度为 $nex_{~j-1}$ .

第一条性质推导出的引理就是，在匹配过程中只需判断下一位是否相同，若否则直接进行失配处理即可；而第二条性质保证了失配过程中我们可以通过回溯的方式快速找到满足相同前缀的 k 的最小值。

vector<int> check(string a)
{
	int n=a.size(),p=0; 
    vector<int> pr(n);  pr[0]=0;
	for (int i=1;i<n;i++) {
		while (p && a[p]!=a[i]) p=pr[p-1];
		if (a[p] == a[i]) ++p; pr[i]=p; 
	}
	return pr;
}

3. 算法流程

和上面如出一辙，只不过不再是前后缀的匹配，而是文本串和模式串的匹配。若失配，则模式串立刻利用 nex 数组，跳回其最长前缀重新匹配。

vector<int> kmp(string a,string s)
{
	nex = check(a);	int n=a.size(),p=0;
	vector<int> pr;
	for (int i=0;i<s.size();i++) {
		while (p && a[p]!=s[i]) p=nex[p-1];
		if (a[p] == s[i]) ++p; 
		if ( p==n ) pr.push_back(i-n+1);
	}
	return pr;
}

4. 扩展 KMP（Z 函数）

摸。

叁. AC 自动机

1. 解决对象

在线性时间内快速解决多模式串的匹配问题。

本质上确实就是 Trie 树 + KMP，但在细节上对这两个算法进行了多角度融合。

2. fail 指针与 fail 边

定义 $tr_{(i,c)}$ ：对编号为 i 的节点，以 c 为下一字符的子节点编号。亦或是对于编号为 i 所映射的字符串 S，以 s 为下一字符所形成字符串的映射函数。第二种定义更有利于我们去理解字典图的意义。

$tr(i,c)$ 本质上便是Trie 树的搭建过程，我们令编号 0 为该树的根节点。

定义 $fail_u$ ：对于编号为 u 的节点，匹配该字符串的最长后缀所对应的节点编号。与 $nex_i$ 不同的是，该指针可以指向任意模式串，且仅仅包涵最长后缀的信息而非前后缀。

fail 指针的构建同样利用 KMP 中 “回溯” 的思想，对于节点 u 及其子节点 $v=tr_{(u,c)}$ ，我们令 $fail_v=tr_{(fail_u,c)}$ ；如果该点不存在，我们就向上回溯， $u_1=fail_u$ ，匹配 $tr_{(u_1,c)}$ …如此下去。直至回到根节点。

但我们的代码异常简单：

void build()
{
	queue<int> q; 
	for (int i=0;i<26;i++)
		if (tr[0][i]) q.push(tr[0][i]),fail[tr[0][i]]=0;
	while (!q.empty()) {
		int k=q.front(); q.pop();
		for (int i=0;i<26;i++) 
		if (tr[k][i]) fail[tr[k][i]]=tr[fail[k]][i],q.push(tr[k][i]);
		else tr[k][i]=tr[fail[k]][i];
	}
}

我们可以注意到，里面并没有出现回溯的过程，而且 else 后面跟着的还有一个奇怪的东西。但其实短短的一行代码，却已经完成了 字典图 的搭建，并且极大提升了算法的效率。

我们在任何AC自动机博客中总能看到很恐怖的字典图：

但其中的黑边本质上只是一个 “搭桥”的过程，这就是else 语句所起的作用。

我们对于 Trie 树进行广搜，保证了我们总能将深度较小的节点优先处理，即假设对于 dep=3 的节点，我们的桥总是往 dep=1,2,3 上搭。

而对于一个节点，若要抹去回溯过程，最简单的方式便是 在回溯路径上就提前把边连好，等到你要回溯了就可以走刚搭好的小路。具体来说就是如果当前节点 u 没有某种字符的子节点，我们就引一条边到其 $fail_u$ 对应字符的子节点。这个可类比并查集的路径压缩来理解，我们管这个叫 fail 边。

3. 查询操作

基本上没啥问题了，直接在 Trie 图上跑，同时利用 fail 指针找出所有相同后缀的字符串映射的编号。

关于统计模板题答案啥的，标记一下所有叶子节点，搜到了就 ans++ 即可。

#include <bits/stdc++.h>
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define cle(x) memset(x,0,sizeof(x))
#define inf 2147483647
#define ll long long
using namespace std;

const int maxn=2000100;

#define str s[i]-'a'
string s[maxn];
int n,st,mp[maxn],vis[maxn],sum[maxn],fail[maxn],tr[maxn][30];

void insert(string s,int x)
{
	int now=0;
	for (int i=0;i<s.size(); now = tr[now][str], i++) 
	if ( !tr[now][str] ) tr[now][str] = ++st;
	if ( !vis[now] ) vis[now] = x; mp[x] = vis[now];
}

void build()
{
	queue<int> q; fail[0]=0; 
	for (int i=0;i<26;i++) 
		if (tr[0][i]) fail[ tr[0][i] ]=0, q.push(tr[0][i]);
	while (!q.empty()) {
		int k=q.front(); q.pop();
		for (int i=0;i<26;i++) {
			if (tr[k][i]) 
				fail[tr[k][i]] = tr[fail[k]][i], 
				q.push(tr[k][i]);
			else tr[k][i]=tr[fail[k]][i];
		}
	}
}

void query(string s)
{	int now=0,p=0;
	for (int i=0;i<s.size();i++)
	{
		now = tr[now][str];  p = now;
		while (p) sum[ vis[p] ]++ , p = fail[p];
		//只有模式串结尾才会有贡献。 
	} 
}

int main()
{
	cin>>n;
	for (int i=1;i<=n;i++) cin>>s[i],insert(s[i],i);
	build(); cin>>s[0]; query(s[0]);
	for (int i=1;i<=n;i++) cout<<sum[ mp[i] ]<<endl;
}

4. 时间复杂度分析

很多题解骗我说这种裸的 AC 自动机的时间复杂度是 $O(S_0+\sum s_i)$ ，其中 $S_0$ 是文本串的长度， $s_i$ 是模式串的长度。既然如此，为啥我过不了AC自动机的二次加强版呢！！

我们先考虑对于模式串，其构造 Trie 图的时间。主要由 “插入” 及 “连 fail 边” 两部分组成。插入显然 $O(\sum s_i)$ ，连 fail 边时候每个节点都会入队列，把每个字母都询问一遍，也显然是 $O(26*\sum s_i)$ 。

而对于文本串匹配，时间复杂度也可能由两个部分导致：沿着 Trie 图转移；沿着 fail 指针找出所有可匹配模式串。

沿着 Trie 图显然 $O(S)$ ，貌似很正常。
但沿着 fail 指针很明显就有问题：

一. 大量的点肯定都不是模式串的终点，由此进行了许多无效操作；
二. 对于a,aa,aaa... 匹配 aaaa... 的情况便可能卡到 $O(S*s_i)$ 。

5. fail 树优化

最大的阻碍在于问题二，其中每个节点都经过了 $O(S)$ 次，最终导致 TLE。而造成问题二的原因又隐藏在问题一里：咱们跳 fail 指针的姿势有问题。

接下来引用自知乎专栏：

一个结点只有一个 fail 指针指出，可能被多个 fail 指针指向；因此，fail 指针构成了一个以 0 为根的fail 树，一个结点的 fail 指针指向它在 fail树中的父亲。

先给出如下两个定义：

某结点在AC自动机的匹配过程中作为一个被转移的状态，称此结点为 直接匹配；
被访问的结点沿着fail指针遍历到的结点，称为可被匹配。

那么这个模式串被匹配到的次数，就是它的终点 直接匹配次数+可被匹配次数。

而对于 fail 树任意一个节点 u，若其子树内某个节点 v 被直接匹配，那显然的是该节点可以顺着 fail 指针一直爬，爬到节点 u 从而将其间接匹配 。

换句话说，fail树中某结点 直接匹配次数+可被匹配次数，也就等于 以它为根的子树中所有结点直接被匹配的次数。

这样，我们先不沿着fail指针寻找，而是在每个结点保存一个计数器，计算被匹配到的次数，等到文本串匹配完毕再一并从fail树的叶子结点向上传递，那么就可以把多次沿着fail的遍历合并为一次，复杂度就大大降低。

#include <bits/stdc++.h>
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define cle(x) memset(x,0,sizeof(x))
#define inf 2147483647
#define ll long long
using namespace std;

const int maxn=2000100;

#define str s[i]-'a'
string s[maxn];
int n,st,mp[maxn],vis[maxn],siz[maxn],fail[maxn],tr[maxn][30];
vector<int> g[maxn];

void insert(string s,int x)
{
	int now=0;
	for (int i=0;i<s.size(); now = tr[now][str], i++) 
	if ( !tr[now][str] ) tr[now][str] = ++st;
	mp[x] = now;
}

void build()
{
	queue<int> q; fail[0]=0; 
	for (int i=0;i<26;i++) if (tr[0][i]) fail[ tr[0][i] ]=0, q.push(tr[0][i]);
	while (!q.empty()) {
		int k=q.front(); q.pop();
		for (int i=0;i<26;i++) {
			if (tr[k][i]) fail[tr[k][i]] = tr[fail[k]][i], q.push(tr[k][i]);
			else tr[k][i]=tr[fail[k]][i];
		}
	}
}

void query(string s)
{	int now=0,p=0;
	for (int i=0;i<s.size();i++)
		now = tr[now][str],++siz[now]; 
	for (int i=1;i<=st;i++) g[ fail[i] ].push_back(i);
}

void dfs(int u)
{
	for (auto v:g[u]) dfs(v),siz[u]+=siz[v];
}

int main()
{
	cin>>n;
	for (int i=1;i<=n;i++) cin>>s[i],insert(s[i],i);
	build(); cin>>s[0]; query(s[0]);  dfs(0);
	for (int i=1;i<=n;i++) cout<<siz[ mp[i] ]<<endl;
    //这里的 mp_i 已从点到点的映射转换为点到边的映射
}

6. 例题

【POI2000】病毒

题意：

给定一系列模式串，判断是否存在一个无限长的字符串使不含任何模式串为子串。

分析：

关于我们建好的AC自动机里那些 fail 边与 fail 指针，都是帮助我们在失配的时候能快速切换模式串后缀，从而加快找到匹配效率；

而在这里我们要利用 fail 边与 fail 指针，无限制地在 Trie 图里面绕，直至走过的路成了环，这样我们只要按照该路线就可以构造出满足要求的字符串。这可以通过 dfs 打标记的方式实现。

同时，我们为了避免匹配成功，要避开一切模式串终点；同时，我们也要避开有 fail 指针指向这些终点的节点，因为这意味着该节点所映射的字符串的后缀就是其中的一个模式串，那自然是不允许的。

#include <bits/stdc++.h>
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define cle(x) memset(x,0,sizeof(x))
#define inf 2147483647
#define ll long long
using namespace std;

const int maxn=300010;
#define str s[i]-'0'
int n, st, tr[maxn][3], fail[maxn], sum[maxn], vis[maxn];
string s[3000];  bool v[maxn], ans=0;

void insert(string s,int x)
{	int now=0, l=s.size();
	for (int i=0;i<l;now = tr[now][str], i++) 
		if (!tr[now][str]) tr[now][str] = ++st;
	vis[now] = x;
}

void build()
{
	queue<int> q; int now = 0;
	for (int i=0;i<2;i++) if (tr[0][i]) q.push(tr[0][i]);
	while (!q.empty()) {
		int k=q.front(); q.pop();
		for (int i=0;i<2;i++)  
		if (tr[k][i]) 
			q.push(tr[k][i]), fail[tr[k][i]] = tr[ fail[k] ][i]; 
			vis[ tr[fail[k]][i] ] && ( vis[ tr[k][i] ] = vis[ tr[fail[k]][i] ] );	
			else tr[k][i] = tr[ fail[k] ][i];
	}
}

void dfs(int x)
{
	if (ans) return; if (v[x]) {ans=1;return;} v[x] = 1;  
	for (int i=0;i<2;i++) 
		if (!vis[tr[x][i]]) dfs( tr[x][i] );  v[x] = 0;
}

int main()
{
	cin>>n; for (int i=1;i<=n;i++) cin>>s[i], insert(s[i],i);
	build();  dfs(0); 
	cout<< (ans?"TAK":"NIE") <<endl;
}

【NOI2011】阿狸的打字机

题意： 给定一系列操作和查询，问当前第 x 个字符串在第 y 个中出现多少次。

分析： 先把所有询问离线并按照 y 排序，按输入要求建 Trie 图。在路径上打上 “加一” 标记（因为此时为目标匹配串），当搜索到该串结尾时一并处理所有的 x 子树即可。

啥，你告诉我搜索子树要 O(n)，那就直接利用 dfs 序，放到树状数组上即可。

Viedo Game G
题意： 给定 n 个字符串，让你构造一个长为 k 的文本串，使得这些字符串在该文本串出现的次数最多。
分析：
首先是一个多模式字符串匹配，那应该往 AC 自动机上靠；考虑往一个已知串内加入一个字符使其增加的出现次数更多，这应该是一个 DP 的过程。

那就设 $f[i][k]$ 是 “长度为 i，此时在节点 k 上的最优得分”，考虑转移到下一个节点所能增加的次数，那么以该字符为结尾所产生的贡献是可以算出来的。

但要注意的是，一个节点对应字符串能够造成的贡献，要包含其后缀所能造成的贡献（即 fail[i] 的贡献）。

注意一下初始化，这样能保证仅能从源点开始走：

memset(f,-63,sizeof(f)), f[0][0] = 0;

肆. 后缀数组

学习后缀数组要首先明确两个概念：子串和后缀。具体来说，子串指的是字符串中从 $s_i$ 到 $s_j$ 连续组成的字符串（其中 $1 \leq i \le j \leq size)$ ；后缀 i 指的是从第 i 个字符开始一直到字符串末尾所形成的的子串。

后缀数组由两部分组成： $sa_i$ 与 $rk_i$ 。其中 $sa_i$ 表示所有后缀按字典序排序后，排名第 i 小的后缀编号； $rk_i$ 指的是后缀 i 在 sa 数组里的排名。由上可知，sa 与 rk 数组其实是互逆的。

不论后缀数组有什么功能，我们先考虑如何求解 $sa$ 数组。

1. O(n* log^2 n) 算法

利用倍增思想，假设我们已知长度为 w 的所有子串的排名，那么我们以 $rk_i$ 与 $rk_{i+w}$ 为第一、第二关键字排序，就可以求出长度为 2w 的所有子串的排序。

#include <bits/stdc++.h>
using namespace std;

const int N = 1000010;
string s;
int n, w, sa[N], rk[N << 1], ork[N << 1];

int main()
{
    cin >> s;
    int n = s.size();
    s = '!' + s;
    for (int i = 1; i <= n; i++) sa[i] = i, rk[i] = s[i];
	//处理出所有长度为 1 的子串的排名

    for (w = 1; w < n; w <<= 1) {
        sort(sa + 1, sa + n + 1, [](int x, int y) {
            return (rk[x] == rk[y] ? rk[x + w] < rk[y + w] : rk[x] < rk[y]);
        }); //利用快排实现对长度为 2w 子串的排序
        memcpy(ork, rk, sizeof(rk));
        for (int p = 0, i = 1; i <= n; i++) {
            if (ork[sa[i]] == ork[sa[i - 1]] &&
                ork[sa[i] + w] == ork[sa[i - 1] + w]) rk[sa[i]] = p;
            else rk[sa[i]] = ++p;  //若两子串完全相同，排名也应该相同。
        }
    }
    for (int i = 1; i <= n; i++) cout << sa[i] << " ";
    return 0;
}

2. 基数排序

突兀的插入一个基数排序，它是一种以关键字排序为核心的稳定排序算法。

基数将待排序的元素拆分为 k 个关键字，
先对第 k 关键字进行稳定排序，再对第 k-1 关键字进行稳定排序，再对第 k-2 关键字进行稳定排序……
最后对第一关键字进行稳定排序，这样就完成了对整个待排序序列的稳定排序。

对于一般的排序，我们只需要以每一位作为关键字排序即可。具体代码如下：

void radix_sort()
{
	const int base = 10;
    int exp=1, mx=0;
    for (int i=1;i<=n;i++) mx = max(mx,a[i]);
    while (mx/exp) {
        int t[base] = {0};  //对每一个关键字建桶
        memcpy(a, b, sizeof(b));
		//备份后便于更新。
        for (int i=1;i<=n;i++) t[(b[i]/exp)%base] ++;
        for (int i=1;i<base;i++) t[i] += t[i-1];
		//累加得出排名
        for (int i=n;i>=1;i--) a[t[(b[i]/exp)%base]--] = b[i];
        //为保证原来在后面的仍在后面（维持稳定性），需要倒着搜索。
        exp *= base;
    }
}

3. O(n*logn) 算法

发现瓶颈在排序，我们需要一个 O(n) 的排序算法。看到关键字排序就想到了 基数排序：对于任一长度 2w 的所有子串，先对第二关键字（后半段 w 的子串）排序，排完后再按第一关键字（前半段 w 的子串）排。

我们能发现第一、二关键字本质上并无区别，不过是进行了一个平移的操作。平移超出 n-w 的部分第二关键字就是个 0，放在首部即可。
这样我们只需要进行一次关键字排序即可完成对于 2w 长度的排序了。

#include <bits/stdc++.h>
#define cle(x) memset(x, 0, sizeof(x))
#define ok cout << '!' << endl
#define inf 2147483647
#define ll long long
using namespace std;

const int N = 1000010;
string s;
int n, w, p, i, sa[N], id[N], bu[N], t[N], rk[N << 1], ork[N << 1];

int main()
{
    int m = 300;  // 值域边界
    cin >> s, n = s.size(), s = '!' + s;
    for (i = 1; i <= n; i++) ++t[rk[i] = s[i]];
    // rk -> 第一关键字时子串i的排名
    for (i = 1; i <= m; i++) t[i] += t[i - 1];
    for (i = n; i >= 1; i--) sa[t[rk[i]]--] = i;
    // sa -> 按第一关键字排序后排名i的编号

    for (w = 1; p < n; w <<= 1, m = p) {  // m = p , 缩小值域
        for (p = 0, i = n; i > n - w; i--) id[++p] = i;
        for (i = 1; i <= n; i++)
            if (sa[i] > w) id[++p] = sa[i] - w;
        // id -> 按第二关键词排序后排名i的编号

        memset(t, 0, sizeof(t));
        for (i = 1; i <= n; i++) ++t[rk[id[i]]];
        for (i = 1; i <= m; i++) t[i] += t[i - 1];
        for (i = n; i >= 1; i--) sa[t[rk[id[i]]]--] = id[i];
        //基数排序；此时应以第二关键字排序后的顺序进行

        memcpy(ork, rk, sizeof(rk));
        for (p = 0, i = 1; i <= n; i++) {
            rk[sa[i]] = (ork[sa[i]] == ork[sa[i - 1]] &&
            ork[sa[i] + w] == ork[sa[i-1] + w]) ?p :++p;
        }
    }
    for (i = 1; i <= n; i++) cout << sa[i] << " ";
    return 0;
}

4. 重要应用：Height 数组

给出以下定义：

LCP（最长公共前缀）：两个字符串 S 和 T 的 LCP 是最大的 x 使得 Si = Ti (for any 1<=i<=x)。
lcp(i,j) 函数：后缀 i 与后缀 j 的 LCP.
height[i] = lcp(rk[i], rk[i-1])，即第 i 名后缀与前一名后缀的LCP；h[i] = height[rk[i]]，即 后缀i 与 排名 rk[i]-1 后缀 的LCP。

根据一下引理可求出 height 数组： $h[i] \geq h[i-1]-1$ （感性理解，假设 i-1 的后缀有 height = t，那么 i 的后缀少了一位，至多减小 1 的长度）

利用该引理，我们每次从 h[i]-1 重新匹配 LCP，可以将时间复杂度控制在 O(n).

void getH()
{
	for (int i=1,k=0,j=0;i<=n;i++) {
		if (k) k--; 
		j = sa[rk[i]-1];
		while (s[i+k]==s[j+k]) k++; 
		height[rk[i]] = k;
	}
}

而利用 SA 解决的字符串匹配题，通常是要先将其后缀排序，在根据相邻的 Height 数组整一堆性质（待补充）：

两子串的 LCP 可由 height 数组求出：

LCP(sa_i, sa_j) = \min_{i+1\le k \leq j} height_k

该性质利用了一个引理：对于某个后缀，其最大的 LCP 必为与其 排名差一 的后缀，那么这个性质就可以感性理解了。对于 两个字符串的最长公共子串，也可以通过用非法字符#合并的方式转化为这种模型。

可以利用数据结构将问题优化至 log，如 “喵星球上的点名”。

求字符串内 不同子串 的数目 / 对不同子串进行处理：

这里 不同子串 的含义是长度不同或其中至少一个字符不同；
已知后缀排序后， Height 数组表示的是当前和上一个后缀的最长公共前缀，那么我们完全可以跳过其 LCP，从 $sa_i+height_i+1$ 的部分开始往后处理，如 Good Substrings.

几道例题：

一。喵星球的点名
题意： 给定一系列文本串和询问串，对于每一个询问串回答它在多少个文本串中出现过（即子串）；对于每一个文本串回答它被多少个询问串所询问。

分析： 字符串匹配问题用 SA 解通常就是先连接成大字符串，再后缀排序用 Height 数组求 LCP 的方法来做。显然在后缀排序中，后缀有相同前缀的子串会连续出现，那么对于每一个询问串，我们只需要在 sa 数组上找到对应的询问区间即可。

那么对于一段询问区间，我们可以先打好标记确定每一个后缀属于哪个文本串，然后求出询问 区间内有多少个不同的编号 即可。很久以前貌似做过区间求不同种类数的题，直接套上板子（HH的项链）。

对于第二个问，等价于 每个编号被多少个询问区间覆盖，把询问区间差分处理。但直接累加每一个编号会重复，所以还得套用上一问的思想，保证 只有最靠近左区间端点的编号会产生贡献，我们每次更新一个编号 x 时，加上 sm[i] - sm[pos[x]] 的贡献，若 i 和 pos_x 处于同一询问区间，那么相减后便不产生贡献。

二。Good substrings
题意： 定义一些字母是 “不好的”，若一个字符串中 包含不超过 k 个不好的字母，则这个字符串是 “好的”。给定一个字符串，求其不同的好子串数。

分析： S 长度数量级是 $10^3$ ，可以在 O(n^2) 内枚举所有子串处理。对于不好的字母数，可以通过前缀和直接求出；而对于 不同的子串，可以利用 SA 数组跳过其 height 前缀直接处理。这个还是很典型的，下次要会写。

伍. 后缀自动机（SAM）

1. 定义

学习后缀自动机，我们首先需要知道什么是 确定有限状态自动机（DFA）。

一个 DFA 由五部分构成：

字符集（ $\sum$ ），该自动机只能输入这些字符。
状态集合（ $Q$ ），如果把一个 DFA 看成一张有向图，那么 DFA 中的状态就相当于图上的顶点。
起始状态（ $st$ ），字面意思。
接受状态集合（ $F$ ），是一组特殊的状态，也可视作 终止状态。
转移函数（ $\delta$ ），记作 $v_1 = \delta (v_2, ch)$ ， $v_1$ 和 $v_2$ 表示两个状态，体现字符串在 DFA 上的转移。若把一个 DFA 看成一张有向图，那么 DFA 中的转移函数就相当于连边，而每条边上都有一个字符。

特别地， ch 可以扩展为一个字符串 s，表示 $\delta(\delta(\delta(...,s[n])...s[1]),s[0])$ 。

更特别地， $SAM(s) = \delta(st, s)$ 。

简单地可以把 DFA 视作一个有向图，它实现的是对字符串的识别。DFA 从起始状态 $st$ 与目标串 A 进行匹配，如果 A 可以完全匹配则称 DFA 接受了 A，记作 DFA(s).

而对于一个称作 SAM 的 DFA，我们有：

SAM(s) \iff s 是 A 的后缀

最显然的一条性质是： s 是子串当且仅当 s 对应了 SAM 上的路径。SAM 不唯一，因此我们得构造一个跑的最快的， $O(n)$ 的最好。

2. `Endpos` 等价类

我们定义一个子串 s 的 endpos 集合定义为：所有 s 出现位置的右端点 的集合。
同理，endpos等价类 表示具有相同 endpos 集合的字符串所组成的集合。

特别地， $endpos(st) = \left \{ -1, 0,..., |S|-1 \right \}$ .

显然的是，如果 u,w (u <= w) 两个字符串的 endpos 相同，u 一定是 w 的一个后缀。更进一步，若 endpos(u) 和 endpos(w) 有交集，则下面两个命题之一成立：

endpos(u) \subseteq endpos(w) \\ endpos(u) \cap endpos(w) = \varnothing

为了描述一个 endpos 等价类在 SAM 中的状态，我们定义 max/min(v) 表示状态 v 所对应所有的字符串中最长和最短的那个。那么，v 对应的任意一个字符串都是 max(v) 的后缀，且不是 min(v) 的真后缀。并且，v 包含了所有这样的字符串。

3. `Parent` 树

根据上面的芝士，我们知道对于任意两个串的 endpos 集合，要么属于包含关系，要么交集为空。根据这个性质可以构造出一个由包含关系所构成的 Parent 树。

对于 w 所有的后缀按长度降序，那么一定存在前几个后缀包含于w的 endpos 等价类中，而且是后面的等价类的真子集。

因此，定义 link(v) 表示 v 的后缀中属于另一等价类的最长的 那个状态。用集合的语言来说，即：找到最长的后缀 t，使得 endpos(v) 是 endpos(t) 的真子集。

当然找法也很简单，确定 endpos(v) 等价类的 min(v)，那么有：

|min(v)| = |max(link(v))| + 1

特别地，起始点 st 是 Parent 树的根。Parent 树也反映了 endpos 集合的包含关系。

4. SAM 构造算法

SAM 的构造是在线的，可以在均摊 O(1) 时间内向 SAM 中添加一个字符。

先证明一个引理：若状态 v 有字符 c 的转移，则它在 parent 树上的祖先都有。 证明可由 endpos 集合的定义出发，自证不难。

因此有如下构造：

加入一个字符 $x_i$ 时，我们先创建一个新状态 cnt，这个状态刚插入时代表 right 集合 {i}，同时维护上一个加入的状态 p；
根据上述引理，当 p 没有字符 c 转移时向上跳 link，并对于每一个祖先节点向 cnt 连边。
若不存在 p，说明这个字符之前没出现过，直接向 st 连边即可；否则执行下一步。
令 p 存在字符 c 转移且转移的节点为 q（形式化地， $q=\delta (p,c)$ ）。若 len[q] = len[p]+1，说明当前的转移是 连续的，此时将 par[cnt]=q 即可；否则执行下一步。
创建一个新状态 clone，将 q 的 后缀链接与转移 信息复制给 clone，且 len[clone] = len[p]+1；将 cnt 和 q 的 link 指向 clone；将 p 及 q 的祖先所有连向 q 的出边改成 clone。

5. 一系列证明

正确性证明：

前三步的正确性显然，我们考虑已经存在转移时的情况。
由 link(v) 的性质可知，我们应该链接的对象应满足 len[q] = len[p]+1，若不满足则将其拆成两个节点，p 和 q 通过 clone 进行一次迭代，可以证明迭代总数量不超过 n。

状态数线性证明：

对于一个长度为 n 的字符串，它的 SAM 中的状态数 不会超过 2n-1 （假设 n>2）。

算法本身即可证明该结论。一开始，自动机含有一个状态，第一次和第二次迭代中只会创建一个节点，剩余的步中每步会创建至多个状态。

对于一个长度为 n 的字符串，它的 SAM 中的转移数不会超过 3n-4（假设 n>3 ）。

考虑SAM的任意一个生成树，那么SAM上的边就会被分成树边和非树边。

树边最多只有 2n−2 条。
每条非树边 (u,v) 可以找到起始状态到 u 的树上路径，也能找到 v 到接收状态的路径，则非树边对于后缀形成一个单射。而后缀数量为 n-1。（形如 abb..bb）

6. 代码

void insert(char c)
{
    int now = ++sz, p = lst;
    tr[now].len = tr[p].len+1;
    while (p!=-1 && !tr[p].nex.count(c))
        tr[p].nex[c] = now, p = tr[p].lk;
    if (p == -1) tr[now].lk = 0;
    else {
        int q = tr[p].nex[c];
        if (tr[q].len==tr[p].len+1) tr[now].lk=q;
        else {
            int clo = ++sz;
            tr[clo].len=tr[p].len+1;
            tr[clo].lk =tr[q].lk;
            tr[clo].nex=tr[q].nex;
            while (p!=-1 && tr[p].nex[c] == q)
                tr[p].nex[c] = clo, p = tr[p].lk; 
            tr[now].lk = tr[q].lk = clo;
        }
    }
    lst = now;
}

void SAM(string a)
{
    tr[0].len=0, tr[0].lk=-1;
    sz = lst = 0;
    for (int i=0;i<n;i++) insert(a[i]);
}

int find(string s)
{
    int now=0, num=0, ans=0;
    for (int i=0;i<m;i++) {
        if (tr[now].nex.count(s[i])) 
            now = tr[now].nex[s[i]], num++;
        else {
            while (now!=-1 && !tr[now].nex.count(s[i])) 
                now = tr[now].lk;
            if (now == -1) now=0, num=0;
            else {
                num = tr[now].len+1, 
                now = tr[now].nex[s[i]];
            }
        }
        ans = max(ans, num);
    }
    return ans;
}

7. 应用

查找两串的最长子串长度（LCS），就是上面的板子；
查找不同子串个数，对于每个新增状态 v，增加的不同字串个数即为 $max(v)-min(v)+1$ ，而又等价于 $max(v)-max(link(v))$ ，递推地求即可。
查询模式串出现次数，根据 link 的性质，在 parent 树上找对应节点子树的出现次数总和即可。
其他可详见 OIWKI .

〇. 字符串哈希

壹. Trie树

1. 普通 Trie 树

2. 可持久化 Trie 树

贰. 前缀函数及 KMP 算法

1. 解决对象

2. 前缀函数

3. 算法流程

4. 扩展 KMP（Z 函数）

叁. AC 自动机

1. 解决对象

2. fail 指针与 fail 边

3. 查询操作

4. 时间复杂度分析

5. fail 树优化

6. 例题

肆. 后缀数组

1. O(n* log^2 n) 算法

2. 基数排序

3. O(n*logn) 算法

4. 重要应用：Height 数组

几道例题：

伍. 后缀自动机（SAM）

1. 定义

2. Endpos 等价类

3. Parent 树

4. SAM 构造算法

5. 一系列证明

正确性证明：

状态数线性证明：

6. 代码

7. 应用

六。完结撒花？

2. `Endpos` 等价类

3. `Parent` 树