字符串学习笔记

KMP 及其相关

见广义 KMP 以及其扩展（Broad Sense Kmp）。

trie 及其相关

普通 trie

这里不再赘述，主要就是插入一个字符串（一个数字），然后进行树上 dp 的一个过程。

可持久化 trie

类似于可持久化线段树的建树过程，复制每个节点，然后对于相应的子节点进行递归处理（线段树是二叉，trie 是 $|C|$ 叉，$C$ 是字符集）

所以建树的过程大概是 $O(\sum |S| \times |C|)$，一般把 $C$ 看做一个常数。（序列除外）

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

void insert(string s,ll s1,ll s2){
	for(ll i=0;i<s.size();i++){
		cnt[s1] = cnt[s2];
		for(ll j=0;j<26;j++) trie[s1][j]=trie[s2][j];
		cnt[s1]++;
		trie[s1][(ll)(s[i]-'a')] = ++tot;
		s1 = trie[s1][s[i]-'a'],s2 = trie[s2][s[i]-'a'];
	}
	cnt[s1] = cnt[s2];
	for(ll j=0;j<26;j++) trie[s1][j]=trie[s2][j];
	cnt[s1]++;
}

$cnt$ 是子树元素个数，然后 $trie_{i,j}$ 就是从 $i$ 经过字符为 $j$ 的边到达的节点，我们就可以愉快地树上 统计/dp 了。

具体操作同线段树，也是处理一个前缀的序列问题（字符串的前后缀，异或的结果等）。

可持久化 trie 大概就是这些。