HDU 5745 La Vie en rose 手写bitset优化DP

http://acm.hdu.edu.cn/showproblem.php?pid=5745

La Vie en rose

Time Limit: 7000/3500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description
Professor Zhang would like to solve the multiple pattern matching problem, but he only has only one pattern string p=p1p2...pm. So, he wants to generate as many as possible pattern strings from p using the following method:
1. select some indices i1,i2,...,ik such that 1i1<i2<...<ik<|p| and |ijij+1|>1 for all 1j<k.
2. swap pij and pij+1 for all 1jk.
Now, for a given a string s=s1s2...sn, Professor Zhang wants to find all occurrences of all the generated patterns in s.
 
Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains two integers n and m (1n105,1mmin{5000,n}) -- the length of s and p.
The second line contains the string s and the third line contains the string p. Both the strings consist of only lowercase English letters.
 
Output
For each test case, output a binary string of length n. The i-th character is "1" if and only if the substring sisi+1...si+m1 is one of the generated patterns.
 

Sample Input

3

4 1

abac

a

4 2

aaaa

aa

9 3

abcbacacb

abc

 

Sample Output

1010

1110

100100100

 Author
zimpha
 Source
 

发表评论

电子邮件地址不会被公开。 必填项已用*标注