ABC299F Square Subsequence
Hell0_W0rld
·
·
题解
ABC299F Solution
题目大意
给定字符串 S，求有多少个 T 满足 TT 是 S 的不一定连续的子串。
解题思路
我们可以观察一个满足条件的 T，发现有可能它在 S 中出现多次，而我们要的只是一次。所以我们 每一次只找离上一个最近的字符。
例如串 \texttt{ababbaba} 中找 T=\texttt{ab}，我们选 \color{red}\texttt{abab}\color{black}\texttt{baba} 而不选 \color{red}\texttt{aba}\color{black}\texttt{bba}\color{red}\texttt{b}\color{black}\texttt{a}。
这样我们令 nxt_{i,c} 表示 i 号字符以后，第一个为 c 的位置是几号。
这样我们就可以 \mathrm{DP} 了：f_{x,p,q} 表示左边上一个为 p 且右边上一个为 q，最终串 T 的最后一个字符落在位置 x 上。转移为：f_{x,p,q}\to f_{x,nxt_{p,c},nxt{q,c}}。转移条件为 nxt_{p,c}<x。
注意当后面没有的时候，也不能转移。
初始状态是什么呢？我们可以取一个 "T 串的 -1 号位置" 0,x 作为起点，这样一定合法。
于是初始为 f_{x,0,x}=1，答案为 \sum^{n-1}_{x=2} \sum^n_{y=x+1} f_{x,x,y}，其中 n 为字符串长度。
复杂度 O(n^3)，可以通过。
code