当前位置:首页 > 字符串 > 正文
洛谷P1819公共子序列[NOI导刊]
101+

题目大意:长度为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$。

解题思路

预处理出每个字符串每个位置后面各个字母最近的位置,这样我们就可以枚举子序列的下一个字母,如果大家都有,就可以尝试匹配更长、更多的子序列。再加个记忆化即可通过此题。

程序实现

洛谷P1819公共子序列[NOI导刊]:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter