5363: Forgiving Matching
内存限制：128 MB
时间限制：40.000 S
评测方式：文本比较
命题人：
提交：6
解决：3
题目描述
Little Q is now checking whether string A matches B. Two strings are considered matched if they have the same length, and there is no position i that Ai is different from Bi.
However, Little Q is a kind man, he forgives every person who hurt him. What's more, he even forgives strings! He gives the string k opportunities, if there are no more than k positions i that Ai is different from Bi, then Little Q will also consider the two strings matched. Note that both of the strings may contain the wildcard character '*', which can match exactly one any character, in such a case this pair won't consume the forgiveness opportunities.
Let's denote occ(S,T) as the number of substrings in string S which matches T, two substrings are considered different if they start in different places. You will be given two strings S and T, write a program to compute the value of occ(S,T) for k=0,1,2,…,|T|.
However, Little Q is a kind man, he forgives every person who hurt him. What's more, he even forgives strings! He gives the string k opportunities, if there are no more than k positions i that Ai is different from Bi, then Little Q will also consider the two strings matched. Note that both of the strings may contain the wildcard character '*', which can match exactly one any character, in such a case this pair won't consume the forgiveness opportunities.
Let's denote occ(S,T) as the number of substrings in string S which matches T, two substrings are considered different if they start in different places. You will be given two strings S and T, write a program to compute the value of occ(S,T) for k=0,1,2,…,|T|.
输入
The first line contains a single integer K (1≤K≤100), the number of test cases. For each test case:
The first line of the input contains two integers n and m (1≤m≤n≤200000), denoting the length of S and the length of T.
The second line contains a string S of length n.
The third line contains a string T of length m.
It is guaranteed that the sum of all n is at most 1000000. Both S and T can only contain the characters in {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '*'}.
The first line of the input contains two integers n and m (1≤m≤n≤200000), denoting the length of S and the length of T.
The second line contains a string S of length n.
The third line contains a string T of length m.
It is guaranteed that the sum of all n is at most 1000000. Both S and T can only contain the characters in {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '*'}.
输出
For each test case, output m+1 lines, the i-th (1≤i≤m+1) of which containing an integer, denoting the value of occ(S,T) when k=i−1.
样例输入 复制
1
5 3
012*4
1*3样例输出 复制
1
1
3
3