洛谷P1819公共子序列[NOI导刊]
979+
作者：crxis 发布：2021-05-10 分类：字符串
题目大意：长度为n的3个字符串，他们有多少个不同的公共子序列？
题目描述
求 $3$ 个字符序列有多少个不同的公共子序列，不包括空序列。
输入输出格式
输入格式
第一行为一个正整数 $n$，表示 $3$ 个序列的长度。
接下来 $3$ 行，每行一个无空格长度为 $n$ 的字符序列。只包含小写字母 `a` 到 `z`。
输出格式
一行一个正整数 $ans$，对 $10^8$ 取模。
输入输出样例
输入样例 #1
4
aabb
abab
baba
输出样例 #1
5说明
对于唯一的一个样例，有 $5$ 种子序列，分别是 `a`，`ab`，`aa`，`bb`，`b`。
– 对于 $30\%$ 的数据，保证 $1 \le n \le 10$；
– 对于 $70\%$ 的数据，保证 $1 \le n \le 50$；
– 对于 $100\%$ 的数据，保证 $1 \le n \le 150$。
解题思路
预处理出每个字符串每个位置后面各个字母最近的位置，这样我们就可以枚举子序列的下一个字母，如果大家都有，就可以尝试匹配更长、更多的子序列。再加个记忆化即可通过此题。
程序实现
