题解：P9753 [CSP-S 2023] 消消乐【哈希，DP】

P9753 [CSP-S 2023] 消消乐

• 当 $|t|=2$，显然 $s$ 不变。
• 当 $|t|>2$ 时，归纳假设：任意长度 $<|t|$ 的合法串的入栈都不会使 $s$ 改变。
  • 当 $t=c_1+a+c_2$，其中 $c_1$ 和 $c_2$ 为两个相等的字符，$a$ 为任意合法串。
    • $c_1$ 入栈时，若和栈顶元素抵消，由于 $a$ 不会使 $s$ 改变，那么 $c_2$ 将会补回抵消的 $c_1$，因此 $s$ 不变。
    • $c_1$ 入栈时，若没有和栈顶元素抵消，由于 $a$ 不会使 $s$ 改变，那么 $c_2$ 将会和 $c_1$ 抵消，因此 $s$ 不变。
  • 当 $t=b_1+b_2+\cdots+b_k$ 时，其中 $b_i$ 为任意合法串。显然 $s$ 不变。

• $|t|=2$ 显然成立。
• $|t|>2$ 时，
  • 显然 $t$ 一定存在相邻两个相等的字符。
  • 把 $t$ 中任意两个相邻相等的字符删去得到 $t'$，$t'$ 的能使栈状态不变，根据归纳假设，$t'$ 是合法串。
  • 显然在合法串任意位置中加入两个相邻相等的字符后还是合法串。

Code

考虑如何求出 $g(i)$，令 $x=i-1$，若 $x>0$ 就不断使 $x\gets g(x)-1$，直到 $s[x]=s[i]$，这时 $g(i)=x$。正确性显然。接下来证明这样跳的复杂度为 $O(n|\Sigma|)$。参考证明

• 设 $j>i$，且以 $x=j-1$ 为起始点，不断跳到 $g(x)-1$，能跳到 $i$。
• 反证法。假设存在 $k>j$，使得 $s[k]=s[j]$，且 $k$ 能跳到 $i$。
• 显然 $s[i+1,j-1]$ 和 $s[i+1,k-1]$ 都是合法串。
• 根据 做法一 中证明的结论，可以发现 $s[j,k-1]$ 是合法串。
• 因此一定存在 $t\in[j+1,k-1]$，使得 $s[t]=s[j]$，且在合法串 $s[j,k-1]$ 中，$t$ 和 $j$ 是匹配的。
• 因此 $s[j,t]$ 是合法串。
• 因此 $s[t+1,k-1]$ 是合法串。
• 又因为 $s[t]=s[j]=s[k]$，于是 $k$ 最多跳到 $t$ 就会停止，不会跳到 $i$。假设不成立。
• 综上所述，每个点最多会被每种颜色中的一个点跳到，故复杂度为 $O(n|\Sigma|)$。

Code

通过简单处理即可做到 $O(n)$。Code