After a lot of Turtle Soup horrible stories and yes/no questions, you want to build up some much more peaceful stories to play with. This time, you're going to be provided with two strings S1 and S2 for you and your friends. (Sounds peaceful, isn't it? ;) But your friends can see only one of them, S1. The other one, S2, however, is kept in secret. The goal of this game is to find out what the secret string S2 is. During the game, your friends can ask you any questions in the form "Does S appear at the position X in the secret string S2?" You may answer "yes" if the string S does appear in S2 as a substring with starting position X, or answer "no" if the string S does NOT appear in S2 at position X. But you have to answer "irrelevant" if S is NOT a substring of S1.
After playing several rounds, you find your friends are boring because they always ask you a "substring" of length 1. Thus you add another rule: if any string S in a question has length less than k, you may answer your friend with "More detail, please."
Here comes the problem, you hope your friends will finally figure out the whole secret string S2, but meanwhile you want the bottleneck length k to be as large as possible. What is the maximum k such that your friend will have any chance to find out the secret string?
For any information about 海龜湯, please find it on TurtleSoup@ptt.
Input consists of several test cases.
For each case, the first line contains S1 and the second line contains S2.
Every string in the input contains only lower case English letters and its length satisfies 1<= length <=500,000.
For each test case, output the maximum k, and then output another number Q indicates the minimum number of questions that your friends have to ask in order to figure out S2.
If it is impossible to find such k then output two zeroes instead.
expectopatronum patrotopaexpec avadakedavra abracadabra
4 3 0 0
被雷到可能會影響您的身心健康，ACM2009培訓班關心您。(按我繼續)
Migrated from old NTUJ.
| No. | Testdata Range | Score |
|---|