学步园

　　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?

　　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 '?'.

　　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.

2
aca
abcd
abb?a
c?c?

Case #1: 9
Case #2: 14

华南师范大学2012年ACM程序设计竞赛（初赛+决赛无尽版）

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define LL __int64
LL t;
LL i,j,k;
LL  a[60];//存储第一个字符串中各字母出现的次数 
LL  b[60];//存储第二个字符串中各字母出现的次数 
char s1[200005];
char s2[200005];

int main()
{
	int  cnt=1;
	cin>>t;
	while(t--)
	{
		scanf("%s%s",s1,s2);
		LL k1=0; //存储第一个子串'？'的个数 
		LL k2=0;//存储第二个子串'？'的个数 
		printf("Case #%d: ",cnt++);
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		
		for(i=0;s1[i];i++)
				if(s1[i]=='?')
					k1++;	
				else
				{
					if(s1[i]>='a'&&s1[i]<='z')
						a[s1[i]-'a']++;
					else
						a[s1[i]-'A'+26]++;
				}	
	
		
		for(i=0;s2[i];i++)
			if(s2[i]=='?')
				k2++;
			else
			{
				if(s2[i]>='a'&&s2[i]<='z')
					b[s2[i]-'a']++;
				else
					b[s2[i]-'A'+26]++;
			}
		i=1;
		LL ans=i<<60;
		LL l=strlen(s1);
		for(i=0;i<52;i++)
		{
			for(j=0;j<52;j++)
			{
				LL temp=0;
				a[i]+=k1;
				b[j]+=k2;
				for(k=0;k<52;k++)
					temp+=b[k]*(l-a[k]);
				ans=min(ans,temp);
				a[i]-=k1;
				b[j]-=k2;
			}
		}
		printf("%I64d\n",ans);	
	}
	return 0;
}