本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-26 20:33:41

:::::info[题目基本信息] 考察：哈希 hashing。
题目简述：
定义匹配字符串如下：

1. 空串是匹配字符串。
2. 若 $\text{p}$ 是一个小写字母，$S$ 是匹配字符串，那么 $\text{p}+S+\text{p}$ 是匹配字符串，其中定义字符串意义下 $+$ 表示连接，下同。
3. 若 $S,T$ 是匹配字符串，那么 $S+T$ 是匹配字符串。

给定一个长度为 $n$ 的由小写字母构成的字符串 $s$，求它的非空匹配子串个数。
数据范围：

• $1\le n\le 2\times 10^6$ ::::: :::::info[闲话] 由于 lca 要求证明结论所以出现了这篇题解。
  显然下面的东西是老师上课讲的。
  ::::: 令 $s_{(l,r)}$ 表示子串 $\displaystyle\sum_{i=l}^rs_i$。
  结论：$s_{(l,r)}$ 是匹配字符串当且仅当处理 $l$ 前和处理完 $r$ 后匹配时用的栈内元素和顺序完全相同。 :::::success[证明] 先证明一个小结论：
• 字符串是否匹配与匹配顺序无关。

::::success[小结论 1 证明] 设一个字符串 $str=\text{p}+a+\text{p}+b+\text{p}+c+\text{p}$，其中 $a,b,c$ 是匹配字符串，$\text{p}$ 是一个小写字母。

• 若匹配第一、四个 $\text{p}$ 和第二、三个 $\text{p}$：
  容易发现 $str$ 是一个匹配字符串。
• 若匹配第一、二个 $\text{p}$ 和第三、四个 $\text{p}$：
  容易发现 $str$ 也是一个匹配字符串。

所以 $str$ 的匹配顺序与是否匹配无关。
:::: 再证明一个小结论：匹配字符串性具有前后缀可减性。更详细地：

1. 若 $S$ 以及 $S_{(1,k)}$（$k\in\mathbb N^*$）都是匹配字符串，那么 $S_{(k,|S|)}$ 也是匹配字符串。
2. 若 $S$ 以及 $S_{(k,|S|)}$（$k\in\mathbb N^*$）都是匹配字符串，那么 $S_{(1,k)}$ 也是匹配字符串。

::::success[小结论 2 证明] 以证明小结论 2-1 为例：
若 $S_{(k,|S|)}$ 不是匹配字符串，那么匹配后的栈非空，那么匹配 $S$ 时的栈就是空栈合并非空栈，也是非空栈，这样 $S$ 就不是匹配字符串，推出矛盾，得证。
小结论 2 类似。
:::: 现在我们可以证明这个结论了。
::::success[充分性] 设 $s_{(1,l-1)}$ 和 $s_{(1,r)}$ 匹配后的栈序列为 $st$，同时设反栈序列为 $\overline{st}$，那么由于小结论 1，$\overline{st}+s_{(1,l-1)}$ 和 $\overline{st}+s_{(1,r)}$ 匹配后栈均为空，所以它们都是匹配字符串，又由于小结论 2，$s_{(l,r)}$ 就是匹配字符串。
:::: ::::success[必要性] 考虑反证法。
如果 $s_{(1,l-1)}$ 和 $s_{(1,r)}$ 的匹配时所用栈序列不同，$s_{(l,r)}$ 匹配时一定添加或删去了一些字符，那么它就不是匹配字符串，推出矛盾。
:::: ::::: 现在我们证明了结论，容易发现这个东西可以哈希。
然后做完了。
时空复杂度均为 $\Theta(n)$。