2023.9.27 Shui_Dream《一类 NPC 问题的多项式时间解法》

给出一个字符串 \(P\)，\(P\) 是由小写英文字母构成的。求总共有多少个不同的字符串 \(Q\)，使得下面两个条件同时成立：

1. 字符串 \(Q\) 非空。
2. 字符串连接得到 \(QQ\)，必须满足 \(QQ\) 是 \(P\) 的子序列。

因为 \(n\le 100\) 很小所以可以直接枚举第二次出现的首位，DP 求这个点两边公共子序列数目，且固定右边那个的起点。

但是这样有巨大多重复，因为没有保证子序列 本质不同。

考虑一种类似 最小表示法，就是 仅用 \(Q\) 在 \(P\) 中的前两次不重复的出现统计答案。

具体来说，枚举第二次出现的首位 \(p\)，然后找 \([1,p)\) 中的字符 \(a_p\) 的第一次出现，设位置为 \(q\)，然后两边都固定起点（分别为 \(q,p\)）跑一遍公共子序列。设 \(f_{i,j}\) 表示两边分别以位置 \(i,j\) 结尾的公共子序列数。

跑的过程中，考虑枚举 \(x\in(i,p),y\in(j,n]\)，要求 \((i,x)\) 中不出现 \(a_x\) 且 \((j,y)\) 中不出现 \(a_y\)，这样 \(f_{i,j}\) 即可转移到 \(f_{x,y}\)。