← 返回题目列表

Codeforces · 1729/G

G. 剪切子字符串

中文机器翻译题面 查看原题

给你两个非空字符串 $$$s$$$ 和 $$$t$$$,由拉丁字母组成。

在一步操作中,您可以选择字符串 $$$s$$$ 中出现的字符串 $$$t$$$ 并将其替换为点。

你的任务是在最小步数中删除字符串 $$$s$$$ 中所有出现的字符串 $$$t$$$,并计算存在多少个不同的最小长度的移动序列。

如果 $$$s$$$ 中删除的字符串 $$$t$$$ 开始出现的索引集不同,则认为两个移动序列不同。例如,集合 $$$\{1, 2, 3\}$$$ 和 $$$\{1, 2, 4\}$$$ 被视为不同,集合 $$$\{2, 4, 6\}$$$ 和 $$$\{2, 6\}$$$ — 也被视为不同,但集合 $$$\{3, 5\}$$$ 和 $$$\{5, 3\}$$$ — 则不然。

例如,让字符串 $$$s =$$$ "abababacababa" 和字符串 $$$t =$$$ "aba"。我们可以通过删除第 $$$3$$$ 和第 $$$9$$$ 位置出现的字符串 $$$t$$$ 来删除 $$$2$$$ 移动中所有出现的字符串 $$$t$$$。在本例中,字符串 $$$s$$$ 是“ab...bac...ba”形式的示例。还可以在第 $$$3$$$ 和第 $$$11$$$ 位置处删除字符串 $$$t$$$ 的出现。有两种不同的最小长度移动序列。

由于答案可能很大,因此输出它对 $$$10^9 + 7$$$ 取模。

输入

输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 50$$$) — 测试用例的数量。各组的描述如下。

每组的第一行包含一个由小写拉丁字母组成的非空字符串 $$$s$$$ ($$$1 \le |s| \le 500$$$)。

每组的第二行包含一个由小写拉丁字母组成的非空字符串 $$$t$$$ ($$$1 \le |t| \le 500$$$)。

保证所有测试用例的字符串长度 $$$s$$$ 的总和不超过 $$$500$$$。同样,保证所有测试用例的字符串长度 $$$t$$$ 的总和不超过 $$$500$$$。

输出

对于每个测试用例,打印两个整数 - 最小移动次数和不同最佳序列的数量,以 $$$10^9 + 7$$$ 为模。

示例

输入 #1

8
abababacababa
aba
ddddddd
dddd
xyzxyz
xyz
abc
abcd
abacaba
abaca
abc
def
aaaaaaaa
a
aaaaaaaa
aa

输出 #1

2 2
1 4
2 1
0 1
1 1
0 1
8 1
3 6

注意

第一个测试用例在语句中进行了解释。

在第二种情况下,删除四个出现中的任何一个就足够了。

在第三种情况下,字符串 $$$s$$$ 是两个字符串 $$$t =$$$ "xyz" 的串联,因此存在唯一的 $$$2$$$ 移动的最佳序列。

在第四种和第六种情况中,字符串 $$$s$$$ 最初不包含字符串 $$$t$$$ 的出现。

在第五种情况中,字符串 $$$s$$$ 恰好包含字符串 $$$t$$$ 的一次出现。