2013编程之美全国挑战赛---相似字符串

对于两个长度相等的字符串，我们定义其距离为对应位置不同的字符数量，同时我们认为距离越近的字符串越相似。例如，“0123”和“0000”的距离为 3，“0123”和“0213”的距离则为 2，所以与“0000”相比，“0213”和“0123”最相似。

现在给定两个字符串 S1 和 S2，其中 S2 的长度不大于 S1。请在 S1 中寻找一个与 S2 长度相同的子串，使得距离最小。

Input

输入包括多组数据。第一行是整数 T，表示有多少组测试数据。每组测试数据恰好占两行，第一行为字符串 S1，第二行为 S2。所有字符串都只包括“0”到“9”的字符。

1 ≤ T ≤ 100

小数据：字符串长度不超过 1000

大数据：字符串长度不超过 50000

Output

对于每组测试数据，单独输出一行“Case #c: d”。其中，c 表示测试数据的编号（从 1 开始），d 表示找到的子串的最小距离。

Sample Input

3

0123456789

321

010203040506070809

404

20121221

211Sample Output

Case #1: 2

Case #2: 1

Case #3: 1解题思路：这道题要求在S1中寻找与S2对应位置相同字符最多的子串。对于小数据，通过枚举子串起点，再按照定义计算距离就可以通过。对于大数据，我们需要更高效的算法。不过看了官方给出的解题报告，用FFT看不懂T_T。如下：如果可以“批量”地计算出S1中所有长度为|S2|的子串与S2的相同字符数量，那么剩下的问题就仅仅是在这些数量值中寻找最大值了。对于S2和S1中的任意一个长度为|S2|的子串，显然这两个字符串相同字符的数量是'0', '1', ..., '9'各自相同字符数的总和，所以我们首先只考虑关于单个字符c的相同字符数量。于是可以把S1和S2看作成两个01序列：字符c对应于1，其他字符对应于0。具体地说，记S1和S2的长度分别为N1和N2，构造两个序列：x[n] = x[n modN1] = (S1[n mod N1] == c) 1 : 0y[n] = (S2[N2 -n - 1] == c) 1 : 0 其中x是循环序列，y对S2头尾调转。聪明的你一定发现了，这两个序列卷积的第n项(x * y)[n]就是S1[n + 1 ... n + N2]与S2相同的c字符的数量，而卷积可以利用FFT在O(NlogN)时间内计算(https://en.wikipedia.org/wiki/Fast_Fourier_transform)。 于是我们可以得到这样一个O(NlogN)的算法：对于每个字符c，构造序列x和y，使用FFT计算卷积，最后把结果相加，找最大值即可。需要注意的是，FFT中涉及的大量sin和cos的计算结果需要提前预处理，否则很容易超时。 因为计算一次卷积需要执行3次FFT，所以上面的算法总共需要执行30次FFT，常数很大。别忘了FFT可以计算复数域的卷积，利用这个特点可以一次处理两种字符c1和c2，只需稍稍修改下x和y的定义。在x中，c1对应于1，c2对应于i，其他字符对应于0；在y中恰好相反，c1对应于i，c2对应于1，其他字符对应于0。若记卷积第n项(x * y)[n]为a + bi，那么b就是c1和c2的相同字符总数。经过这样的修改，计算量减少一半。//////////////////借鉴一个排名第二（chaozicen）的大牛的方法：不过感觉这道题最坏情况也是平方算法，因为有嵌套的for循环，官方给出的能优化到NlogN.

#include  
  #include   
 #include  
   #include  
  #include  
   using namespace std;  
vector e[10];
  int ans[60000];
  int main()  {      int t; 
     cin>>t;   
   int cas=1;   
   while(t--)      {          string s1,s2; 
         cin>>s1>>s2;   
       int len1=s1.size(),len2=s2.size();   
       for(int i=0;i<10;i++)e[i].clear();    
      for(int i=0;i=0)ans[e[ind][j]-i]++;    
          }          }          int dis=0;  
        for(int i=0;idis)dis=ans[i];    
      }          dis=len2-dis;       
   cout<<"Case #"<