A6967 | 字符串大师
时间限制1s
内存限制1024MB
通过 / 提交0/0
题目描述
小明最近迷上了字符串研究。某天，他得到了两个由小写英文字母组成的非空字符串 $S$ 和 $T$。
作为一名充满好奇心的字符串大师，小明立刻提出了一个有趣的问题：
有多少对字符串 $(x, y)$ 满足以下所有条件？
1. $x$ 是字符串 $S$ 的一个子串（Substring）。
2. $y$ 是字符串 $T$ 的一个子序列（Subsequence）。
3. $x$ 和 $y$ 的内容完全相同。
关于“不同”的定义：
- 对于 $S$ 的两个子串 $S[a \dots b]$ 和 $S[c \dots d]$，只要下标区间 $[a, b] \neq [c, d]$，即使它们的内容相同，也视为不同的子串。
- 对于 $T$ 的两个子序列，只要它们选取的字符在 $T$ 中的原始下标集合不同，即使拼接后的内容相同，也视为不同的子序列。
请你帮助小明计算满足条件的对 $(x, y)$ 的数量。由于答案可能非常大，请输出对 $10^9 + 7$ 取模后的结果。
作为一名充满好奇心的字符串大师，小明立刻提出了一个有趣的问题：
有多少对字符串 $(x, y)$ 满足以下所有条件？
1. $x$ 是字符串 $S$ 的一个子串（Substring）。
2. $y$ 是字符串 $T$ 的一个子序列（Subsequence）。
3. $x$ 和 $y$ 的内容完全相同。
关于“不同”的定义：
- 对于 $S$ 的两个子串 $S[a \dots b]$ 和 $S[c \dots d]$，只要下标区间 $[a, b] \neq [c, d]$，即使它们的内容相同，也视为不同的子串。
- 对于 $T$ 的两个子序列，只要它们选取的字符在 $T$ 中的原始下标集合不同，即使拼接后的内容相同，也视为不同的子序列。
请你帮助小明计算满足条件的对 $(x, y)$ 的数量。由于答案可能非常大，请输出对 $10^9 + 7$ 取模后的结果。
输入格式
输入包含两行。
第一行包含一个字符串 $S$ ($1 \le |S| \le 5000$)。
第二行包含一个字符串 $T$ ($1 \le |T| \le 5000$)。
两个字符串均仅包含小写英文字母。
第一行包含一个字符串 $S$ ($1 \le |S| \le 5000$)。
第二行包含一个字符串 $T$ ($1 \le |T| \le 5000$)。
两个字符串均仅包含小写英文字母。
输出格式
输出一个整数，表示满足条件的对 $(x, y)$ 的数量模 $10^9 + 7$ 的结果。
输入输出样例
输入 #1
aa aa
输出 #1
5
输入 #2
codeforces forceofcode
输出 #2
60
提示
样例 1 解释
$S = \text{"aa"}, T = \text{"aa"}$。
满足条件的配对 $(x, y)$ 如下（下标从 1 开始）：
1. $x = S[1 \dots 1]$ ("a"), $y = T[1]$ ("a")
2. $x = S[2 \dots 2]$ ("a"), $y = T[1]$ ("a")
3. $x = S[1 \dots 1]$ ("a"), $y = T[2]$ ("a")
4. $x = S[2 \dots 2]$ ("a"), $y = T[2]$ ("a")
5. $x = S[1 \dots 2]$ ("aa"), $y = T[1, 2]$ ("aa")
共 5 对。
数据范围
- 对于 $100\%$ 的数据：$1 \le |S|, |T| \le 5000$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？