可持久化 trie 树

基本思想

新加入一个字符串后，继承旧版本对应节点的儿子和其它信息，对字符串的每个字符新建节点。

使用方法

两个版本的 trie 树具有可减性，所以可以在静态问题加上区间、树链限制，完成 trie 树可以做的事，比如最大异或、k 大异或、mex 等。

求解区间最大异或时，可以直接比较新旧版本标号是否相等，如果不相等，说明相减后这棵字数非空。

模板代码

inline void insert(int i, int x)
{
	int u = ++ pid, v = root[i - 1], ch;
	root[i] = u;
	for(int i = K; i >= 0; i -- )
	{
		ch = x >> i & 1;
		tr[u][ch ^ 1] = tr[v][ch ^ 1];
		tr[u][ch] = ++ pid;
		u = tr[u][ch], v = tr[v][ch];
	}
}
inline int query(int u, int v, int x)
{
	int cnt = 0, ch;
	for(int i = K; i >= 0; i -- )
	{
		ch = (x >> i & 1) ^ 1;
		if(tr[u][ch] > tr[v][ch])
		{
			u = tr[u][ch], v = tr[v][ch];
			cnt += 1 << i;
		}
		else u = tr[u][ch ^ 1], v = tr[v][ch ^ 1];
	}
	return cnt;
}

KMP

全是神题。

• 给定字符串，求每个前缀最长 border。
• 给定字符串，求周期。
• 给定模式串和文本串，求每个前缀能匹配到的最长模式串，这里指模式串的前缀与文本串的后缀匹配。这种匹配没有单调性。
• 给定模式串和文本串，求文本串每个后缀与模式串的 LCP。（Z 函数）这种匹配有单调性。
• 给定文本串，对文本串进行插入、删除末尾字符的操作，求最长匹配。
  • 一般，next 数组设为前缀最长 border，但真正的 KMP 加上另一个优化：如果 \(s_{i+1}=s_{border_i+1}\)，把 \(next_i\) 设为 \(next_{next_i}\)，因为直接跳到最长 border，一定会适配。这种算法不太好卡，或者有小常数，但时间复杂度还是 \(O(|S|^2)\) 的。快 TLE 去用哈希搞。
  • 如果字符集比较小，可以确定当前匹配的状态末尾加上一个字符之后的状态，建立自动机。时间复杂度 \(O(|S||\Sigma|)\)，\(\Sigma\) 表示字符集。
  • 如果字符集比较小，可以状压加倍增，时间复杂度 \(O(|S|\log|S|)\)。
  • 如果字符集比较小，或者足够有信心，可以直接哈希。
• 给定模式串，对文本串进行插入重复字符、删除末尾多个字符的操作，求最长匹配。
  • 跳转次数不会超过 \(|S|\)，在自动机上倍增，复杂度 \(O((|S|+q)|\Sigma|\log|S|)\)。
  • 对每种字符的转移，自动机是一个森林，并在树根上连自环，可以树链剖分，复杂度 \(O(|S||\Sigma|+q\log|S|)\)。
  • 考虑一种方法压缩字符串：把每个字符相同连续段压缩成一个元素，记录这段字符的种类和长度，然后匹配出去收尾的部分，特判两边。
  • 用哈希匹配。由于字符集比较大，建议双哈希。
• 扩展的匹配：重定义字符串相同
  • 对 next 数组，要求 border 相同，实现时加入两个点后字符串相同。
  • 对匹配过程，要求如果文本串的 \(i\) 在模式串 \(j\) 的位置上，则匹配到的串中，文本串的 \(i\) 与模式串的 \(j\) 相同。

最小表示法

你说得对，但是最小表示法是一款短小精悍的字符串算法，用于判断循环同构，流程如下：

• 将字符串复制一份放后面。
• 两个指针 \(i,j\) 初始分别为 \(0,1\)，记录 \(k\) 表示相同的长度。
• 如果 \(S_{i+k}=S_{j+k}\) 则 \(k\) 增加。
• 如果 \(S_{i+k}\ne S_{j+k}\)，则把较大的指针设为这个指针加 \(k+1\)，\(k\) 设为 \(0\)。
• 当两个指针相等，任意一个加 \(1\)。
• 当一个指针大于 \(n\)，或 \(k\) 大于等于 \(n\)（说明字符串循环），退出循环。
• 两个指针较小一个是最靠前的最小表示。

Z 函数与 Manacher

for(int i = 1, r = 0, p = 0; i < n; i ++ )
{
	if(i < r && z[i - p] < r - i) z[i] = z[i - p];
	else
	{
		z[i] = max(0, r - i);
		while(str[i + z[i]] == str[z[i]]) z[i] ++ , cnt ++ ;
		if(i + z[i] > r) r = i + z[i], p = i;
	}
	ans += z[i] + (i + z[i] != n);
}

inline void change()
{
	s[0] = '#', s[1] = '*', m = 1;
	for(int i = 1; i <= n; i ++ )
	{
		s[ ++ m] = str[i];
		s[ ++ m] = '*';
	}
	s[ ++ m] = '$';
}
inline void manacher()
{
	for(int i = 1, p = 0, r = 0; i <= m; i ++ )
	{
		f[i] = i < r ? min(r - i, f[p + p - i]) : 1;
		while(s[i - f[i]] == s[i + f[i]]) f[i] ++ ;
		if(i + f[i] > r) r = i + f[i], p = i;
	}
}