P5400: 字符串(string)
传统题
1.000s
时间限制
128MB
内存限制
7 提交
5 解决
【题目描述】
题⽬描述
Kri ⾮常喜欢字符串，所以他准备找 t 组字符串研究。
第 i 次研究中， Kri 准备了两个字符串 S 和 R，其中 S ⻓度为 n，且只由 0 , 1 , - 三种字符构成 （注：这⾥的第三种字符是减号）， R初始时为空 。
每次研究，Zay 会带着⼀个美丽的⻓度为 m的字符串 T 来找 Kri 玩，Kri ⾮常羡慕 Zay 拥有如此美丽的 字符串，便也想⽤字符串 S 和 R变出字符串 T。
具体地， Kri 将会进⾏ n 次操作。每次操作中， Kri 会取出S 的第⼀个字符（记为 c），并将其从 S 中 删去。如果 c = - ，则 Kri 要删去 R 的开头字符或结尾字符（数据保证删去后 R 不为空）。否则，
Kri 会将c 加⼊到 R的末尾。
当进⾏完所有操作后， Kri 会检查 R 是否和T相等。如果R=T ， Kri 就会感到开⼼；否则， Kri 会 感到难受。
请问在每次研究中， Kri 有多少种操作⽅式使⾃⼰最后感到开⼼？我们定义两种⽅案不同，当且仅当在 某种⽅案的某次操作中， Kri 删去了R的开头字符。而在另⼀种⽅案的这次操作中， Kri 删去了R的结 尾字符。
由于答案可能很⼤，你只需要输出答案除以 1,000,000,007（即 109+7）的余数。
【输入】
输⼊格式
第⼀⾏⼀个正整数 t。
接下来有t组数据分别表⽰t次字符串的研究，对于每组数据：
第⼀⾏有两个正整数 n,m，分别表⽰字符串S,T 的⻓度。
第⼆⾏是字符串 S。
第三⾏是字符串 T。
【输出】
输出格式
共 t ⾏，第 i ⾏表⽰第i组研究的答案。
【样例输入】复制
3
6 2
10-01-
01
7 3
010-1-1
101
6 4
111-00
1100
【提示】
样例 1 解释
对于第⼀组数据，有以下两种⽅案：
-
第⼀个 - 删R的开头，第⼆个 - 删 R的结尾。
-
第⼀个 - 删R的结尾，第⼆个 - 删R的开头。
附加样例
⻅样例⽬录下的 string2.in 和 string2.out 。
数据范围
对于 20% 的数据， n,m≤15。
对于 30% 的数据， n,m≤30。
对于 70% 的数据， n,m≤80， 。
对于另 10% 的数据， 保证答案不超过 1。
对于 100% 的数据， 1≤t≤5，1≤n,m≤400。