P9753 [CSP-S 2023] 消消乐 题解

zrl123456 · 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[充分性] 设 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)。