Cut Substrings

题意翻译

## 题目描述 给出两个非空字符串$s$和$t$，以最小次数删除使得字符串$s$中不会出现字符串$t$，每次可以将字符串$s$中所有任意一个字符串$t$删除，并且有多少种不同的的方案，如：删除序列$\{1,2,3\}$与删除序列$\{1,2,4\}$是不同的，删除序列$\{2,4,6\}$和删除序列$\{2,6\}$也是不同的，但删除序列$\{3,5\}$与删除序列$\{5,3\}$是相同的 现有$q$次询问，每次输出最小删除次数与以最小删除次数删除的方案数(对$10^9+7$取模) ## 输入格式 第一行是询问次数$q(1\le q \le 50 )$，接下来一行字符串$s(1 \le |s| \le 500)$和一行字符串$t(1 \le |t| \le 500)$ ## 输出格式 $q$行答案，每次输出最小删除次数与以最小删除次数删除的方案数(对$10^9+7$取模) ## 提示 第一个测试用例可以在第$3$个位置和第$9$位置删除，也可以在第$3$个位置和第$11$个位置删除，因此最优删除次数为$2$,有两种方案。 第二个测试用例下，只需要删除$4$个能够匹配的字符串任何一个就足够了 第三个测试用例下，字符串$s=\{xyzxyz\}$是两个字符串$t=\{xyz\}$的串联，因此存在 $2$ 个删除的唯一最优序列。 在第四个和第六个测试用例下，字符串 $s$ 不包含字符串 $t$ 。 在第五个测试用例下,字符串 $s$ 恰好为字符串 $t$ 。

题目描述

You are given two non-empty strings $ s $ and $ t $ , consisting of Latin letters. In one move, you can choose an occurrence of the string $ t $ in the string $ s $ and replace it with dots. Your task is to remove all occurrences of the string $ t $ in the string $ s $ in the minimum number of moves, and also calculate how many different sequences of moves of the minimum length exist. Two sequences of moves are considered different if the sets of indices at which the removed occurrences of the string $ t $ in $ s $ begin differ. For example, the sets $ \{1, 2, 3\} $ and $ \{1, 2, 4\} $ are considered different, the sets $ \{2, 4, 6\} $ and $ \{2, 6\} $ — too, but sets $ \{3, 5\} $ and $ \{5, 3\} $ — not. For example, let the string $ s = $ "abababacababa" and the string $ t = $ "aba". We can remove all occurrences of the string $ t $ in $ 2 $ moves by cutting out the occurrences of the string $ t $ at the $ 3 $ th and $ 9 $ th positions. In this case, the string $ s $ is an example of the form "ab...bac...ba". It is also possible to cut occurrences of the string $ t $ at the $ 3 $ th and $ 11 $ th positions. There are two different sequences of minimum length moves. Since the answer can be large, output it modulo $ 10^9 + 7 $ .

输入输出格式

输入格式

The first line of the input contains a single integer $ q $ ( $ 1 \le q \le 50 $ ) — the number of test cases. The descriptions of the sets follow. The first line of each set contains a non-empty string $ s $ ( $ 1 \le |s| \le 500 $ ) consisting of lowercase Latin letters. The second line of each set contains a non-empty string $ t $ ( $ 1 \le |t| \le 500 $ ) consisting of lowercase Latin letters. It is guaranteed that the sum of string lengths $ s $ over all test cases does not exceed $ 500 $ . Similarly, it is guaranteed that the sum of string lengths $ t $ over all test cases does not exceed $ 500 $ .

输出格式

For each test case print two integers — the minimum number of moves and the number of different optimal sequences, modulo $ 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

说明

The first test case is explained in the statement. In the second case, it is enough to cut any of the four occurrences. In the third case, string $ s $ is the concatenation of two strings $ t = $ "xyz", so there is a unique optimal sequence of $ 2 $ moves. In the fourth and sixth cases, the string $ s $ initially contains no occurrences of the string $ t $ . In the fifth case, the string $ s $ contains exactly one occurrence of the string $ t $ .

**题目大意**：

给定两个非空字符串 $ s $ 和 $ t $，每次操作可以将字符串 $ s $ 中任意一个字符串 $ t $ 替换为点号（.），求使得字符串 $ s $ 中不包含字符串 $ t $ 的最小操作次数，以及在该最小操作次数下有多少种不同的操作序列。例如，删除序列 $\{1,2,3\}$ 与 $\{1,2,4\}$ 是不同的，$\{2,4,6\}$ 和 $\{2,6\}$ 也是不同的，但 $\{3,5\}$ 与 $\{5,3\}$ 是相同的。对于每个测试用例，输出最小操作次数和在该操作次数下的不同操作序列数（对 $10^9+7$ 取模）。

**输入格式**：

第一行包含一个整数 $ q $（$ 1 \le q \le 50 $），表示测试用例的数量。接下来每两行表示一个测试用例，第一行是字符串 $ s $（$ 1 \le |s| \le 500 $），第二行是字符串 $ t $（$ 1 \le |t| \le 500 $）。

**输出格式**：

对于每个测试用例，输出两个整数，分别表示最小操作次数和在最小操作次数下的不同操作序列数（对 $10^9+7$ 取模）。**题目大意**： 给定两个非空字符串 $ s $ 和 $ t $，每次操作可以将字符串 $ s $ 中任意一个字符串 $ t $ 替换为点号（.），求使得字符串 $ s $ 中不包含字符串 $ t $ 的最小操作次数，以及在该最小操作次数下有多少种不同的操作序列。例如，删除序列 $\{1,2,3\}$ 与 $\{1,2,4\}$ 是不同的，$\{2,4,6\}$ 和 $\{2,6\}$ 也是不同的，但 $\{3,5\}$ 与 $\{5,3\}$ 是相同的。对于每个测试用例，输出最小操作次数和在该操作次数下的不同操作序列数（对 $10^9+7$ 取模）。 **输入格式**： 第一行包含一个整数 $ q $（$ 1 \le q \le 50 $），表示测试用例的数量。接下来每两行表示一个测试用例，第一行是字符串 $ s $（$ 1 \le |s| \le 500 $），第二行是字符串 $ t $（$ 1 \le |t| \le 500 $）。 **输出格式**： 对于每个测试用例，输出两个整数，分别表示最小操作次数和在最小操作次数下的不同操作序列数（对 $10^9+7$ 取模）。