再谈字符串

今天对字符串有了一点新的理解，遂再写一篇博客。

注：字符串默认从 $0$ 开始编号。

字符串取模

定义

可以参考 我之前写的博客。不再赘述。下文用长度表示。

运算

$$(S+c)\equiv (S\mathrm{mod}P)+c(\mathrm{mod}P)$$

KMP

定义 $go(i,c)$ 函数，表示 $P$ 的 $i$ 前缀添加字符 $c$ 的字符串的模 $P$ 值。定义失配函数（fail）$f_i$ 表示 $P$ 的 $i$ 前缀时增加的字符 $c$ 失配的模 $P$ 值。

$$go(i,c)=\{\begin{array}{ll}i+1& P_i=c\\ go(f_i,c)& P_i\ne c\end{array}$$

int go(int i, char c)
{
	if(P[i] == c) return i + 1;
	if(i == 0) return 0;
	return go(f[i], c); 
}

...

f[1] = 0;
for(int i=1; i<P.size(); i++)
	f[i+1] = go(f[i], c);
1
2
3
4
5
6
7
8
9
10
11
12

f 数组分析

关于 $f_i$，一方面从自动机角度考虑，即前缀函数 ${\pi }_i$。

一方面从字符串取模的角度考虑，$f_i=P[\mathrm{1..}i)$ 模 $P$ 值。$P[\mathrm{0..}{f}_i)$ 模 $P$ 均为本身，根据定义，$f_i$ 同样满足 ${\pi }_i$ 的性质。

复杂度分析

int cur = 0;
for(int i=0; i<text.size(); i++)
{
	cur = go(cur, text[i]);
	...
}
1
2
3
4
5
6

将 $go$ 函数视为开车，$f_i$ 视为汽油。cur 表示当前油量。

因为 $f_i<i$，所以开车会消耗汽油，$x$ 升汽油最多开车 $x$ 公里。每次增加文本字符，开车或者加 $1$ 升油。显然，加了多少油才能跑多少次，初始为 $0$。由此，时间复杂度为线性 。

例题

[模板] KMP

Censoring S

GT 考试

Prefixes and Suffixes

[CYEZ] So Many Prefix

求字符串前缀出现次数：

设 $t_i$ 表示长度为 $i$ 的前缀出现次数。$t_i=1+{\sum }_{f_j=i}{t}_j$。可通过从后向前递推实现这一过程。

---

无限猴子类技巧

问题形如出现某个模式串 $P$ 的期望长度。

由于只关心匹配，考虑只关心模 $P$ 的值，据此结合待定系数法做期望 dp 即可。

例题

无限猴子

[CTSC2006] 歌唱王国

题解

https://blog.csdn.net/weixin_73113801/article/details/133465423

---

清除模式类技巧

如题，清除字符串中的模式串 $P$。

逐位枚举，考虑当前字符串模 $P$ 的值即可。

例题

清除模式

Pareidolia G