P1819 公共子序列

· · 题解

拿来当自动机练习题了。

考虑怎么构造自动机，发现把每个位置后面的第一个 a\sim z 位置求出来建边，就起到了很完美的去重效果。

显然求一个子串的不同子序列个数直接在图上 dp 就行了。例如 u\to v 则 dp_u 加上 dp_v 的值。

至于三个串无非就是 dp 状态变成了三维，没有啥区别，因为每个点的转移状态都是一样的，都是看能否去到同一个字母。