Description
對於兩個長度相等的字符串，我們定義其距離為對應位置不同的字符數量，同時我們認為距離越近的字符串越相似。例如，“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 <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <stdio.h>
using namespace std;
vector<int> 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<len1;i++)
e[s1[i]-'0'].push_back(i);
memset(ans,0,sizeof(ans));
for(int i=0;i<len2;i++)
{ int ind=s2[i]-'0';
for(int j=0;j!=e[ind].size();j++)
{ if(e[ind][j]-i>=0)ans[e[ind][j]-i]++;
} } int dis=0;
for(int i=0;i<len1-len2+1;i++){
if(ans[i]>dis)dis=ans[i];
} dis=len2-dis;
cout<<"Case #"<<cas++<<": "<<dis<<endl;
} return 0; }
