1718 - Key
Time Limit : 2 Second
Memory Limit : 256 MB
A key is a string consisting of ‘E’, ‘S’, ‘W’ and ‘N’s. Some of keys are called master keys, and the others are called servant keys. Give you one master key KM and N servant keys (S1 to SN). You are asked to determine what the length of the longest prefix which can be found in the master key is for every servant key.
The first line of the input gives the number of test cases T. T test cases follow.
Each test case starts with a line consist of one string representing KM. The next line consists of one integer N. Then N lines follows. The ith line consists of one string representing Si.
1 ≤ |KM| ≤ 106.
1 ≤ N ≤ 104.
1 ≤ |Si| ≤ 102.
KM and Si consists of only ‘E’, ‘S’, ‘W’, and ‘N’.
1 ≤ the total length of all keys in one input file ≤ 4 × 106.
For each test case, first output one line containing “Case #x:”, where x is the test case number.
Then for every servant key, output one line consists of one integer indicating the length of the longest prefix which can be found in the master key.
- sample input
2 SNNSSNS 3 NNSS NNN WSEE NSWWEEW 3 NNSW EEW WWEE
- sample output
Case #1: 4 2 0 Case #2: 1 3 4