Poor Guy Has Came
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 48 Accepted Submission(s) : 8
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
As we known, wangshaobiao is good at solving problems about strings.
One day, zhxfl has written down a problem in his paper.
Given a simple definition of function F(s1, s2) as: the lengths of s1 and s2 are identical, and the value of function F is the number of characters that are not same in s1 and s2.
Then another definition of function G(s1, s2) is given: if the lengths of s1 and s2 are identical, the value of function G is the same as function F; otherwise, suppose s1 is shorter than s2, then the value of function G is the sum of all the F(s1, s), where s is any substring of s2 with length equal to the length of s1. Here we consider the longer string is cyclical.
For example, we have two strings "aca" and "abcd". Obviously there are 4 substrings of "abcd": "abc","bcd", "cda", "dab". So we have F("aca", "abc") = 2 because s1[0]='a' is the same as s2[0]='a', but s1[1] is different of s2[1] and s1[2] is also different of s2[2]. Similarly, F("aca", "bcd") = 2, F("aca", "cda") = 2, F("aca", "dab") = 3. So G("aca", "abcd") = 9.
Our question is simple: given two strings s1 and s2, calculate the value of G(s1, s2).
However, when zhxfl is taking his question happily to find wangshaobiao, the poor guy JYC suddenly come up to do some ugly thing. The poor guy makes his saliva on zhxfl's paper so that some characters have been unable to be read.
Now the question becomes a little complex: let's mark up the unreadable characters as '?' and what's the minimal value of function G?
One day, zhxfl has written down a problem in his paper.
Given a simple definition of function F(s1, s2) as: the lengths of s1 and s2 are identical, and the value of function F is the number of characters that are not same in s1 and s2.
Then another definition of function G(s1, s2) is given: if the lengths of s1 and s2 are identical, the value of function G is the same as function F; otherwise, suppose s1 is shorter than s2, then the value of function G is the sum of all the F(s1, s), where s is any substring of s2 with length equal to the length of s1. Here we consider the longer string is cyclical.
For example, we have two strings "aca" and "abcd". Obviously there are 4 substrings of "abcd": "abc","bcd", "cda", "dab". So we have F("aca", "abc") = 2 because s1[0]='a' is the same as s2[0]='a', but s1[1] is different of s2[1] and s1[2] is also different of s2[2]. Similarly, F("aca", "bcd") = 2, F("aca", "cda") = 2, F("aca", "dab") = 3. So G("aca", "abcd") = 9.
Our question is simple: given two strings s1 and s2, calculate the value of G(s1, s2).
However, when zhxfl is taking his question happily to find wangshaobiao, the poor guy JYC suddenly come up to do some ugly thing. The poor guy makes his saliva on zhxfl's paper so that some characters have been unable to be read.
Now the question becomes a little complex: let's mark up the unreadable characters as '?' and what's the minimal value of function G?
Input
The first line is a number T (1<=T<=50), indicating the number of test cases below.
In each test case, there are two lines. The first line is string s1, and the second line is s2. The length of s1 and s2 will not exceed 200 000. The characters in the strings will be only alphabet(both uppercase and lowercase) letters and '?'.
In each test case, there are two lines. The first line is string s1, and the second line is s2. The length of s1 and s2 will not exceed 200 000. The characters in the strings will be only alphabet(both uppercase and lowercase) letters and '?'.
Output
One line for one test case, containing "Case #D: ?". "D" is the index of the test case, starting from 1, and "?" is the minimal value of function G.
Sample Input
2 aca abcd abb?a c?c?
Sample Output
Case #1: 9 Case #2: 14
Source
华南师范大学·2012年ACM程序设计竞赛·决赛