首页 > 代码库 > 2014牡丹江网络预选赛I题(字符串hash+简单DP)zoj3817
2014牡丹江网络预选赛I题(字符串hash+简单DP)zoj3817
Chinese knot is a decorative handicraft that began as a form of Chinese folk artifact in the Tang and Song Dynasty in China. It was later popularized in the Ming.
Alice is learning Chinese knotting. To take the first step, she went to the store and bought a string. To her surprise, she found the string was composed of characters! Anyway, she made a simple Chinese knot. It consists of one knot with 4 loops:
Look at the picture above. There are four loops connected at the center black knot. To make the image clear and neat, the characters on the string are shown as red and yellow points. As a Mid-Autumn Festival gift, Alice give this handcrafted Chinese knot to you. Then she asked you a question:
You are given a target character sequence. Can you get the sequence by walking on the knot? "Walking on the knot" means:
- You can start at any point you want.
- You can not start at or move to the black knot in the center.
- Each step, you can only move to an adjacent point, except for the point you came from immediately.
- The 8 points closely around the black knot are adjacent to each other. For example, in the picture above, they are the 8 yellow points adjacent to the black knot.
- Your path should not contain three continuous points which are both one of the 8 points mentioned above.
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 (3 <= N, M <= 100000). The total length of string that Alice bought from store is 4 * N.
Then followed by 4 lines, each line contains N lower case letters as a loop of the Chinese knot. These characters are indexed from 1 to 4 * N corresponding to the input order.
The next line contains M lower case letters indicating the target character sequence.
Output
For each test case, output the M indexes of characters you visited. If there are multiple solutions, output any one. If there is no solution, output "No solution!" instead.
Sample Input
2 3 3 abc abc abc abc baa 3 3 abc abc abc abc bab
Sample Output
2 1 4 No solution!
Hint
In the first case, we start at the second character of the first loop and stop at the first character of the second loop.
2014牡丹江网络预选赛I题(字符串hash+简单DP)zoj3817