题目链接：Hamming Distance Sum
题意：
给两个字符串a,b每个字符串只包含字符1和0。求字符串b的每一个长度和a相同的连续子串与a的汉明距离和。
- The Hamming distance between two strings s and t of equal length is defined as.
- find the sum of the Hamming distances between a and all contiguous substrings of b of length|a|.
分析：
两层嵌套循环果然TLE了！又没自己做出来，╮(╯▽╰)╭！看了网上的解题报告。
可以这样想，对于这题而言，每个b的连续子串和a的汉明距离即是不相同的字符个数。
再来看看a的移动比较。
a[0]是和b[0],b[1],...,b[lenb-lena]比较，所以单对a[0]的汉明距离是b[0]到b[lenb-lena]中字符不是a[0]的个数。
a[1]是和b[1],b[1],...,b[lenb-lena+1]比较，所以单对a[1]的汉明距离是b[1]到b[lenb-lena+1]中字符不是a[1]的个数。
....所以可以开一个数组cnt[maxn][2]，其中cnt[i][0]：到位置i（包括位置i）字符串b中字符0的个数；cnt[i][1]：到位置i（包括位置i）字符串b中字符1的个数；位置即代表下标，都是从0开始的。
注意：
- 在计算单对a[i]的汉明距离是ans要加上对b[i]字符的判断，因为cnt数组是包含位置i的
CODE:
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;const int maxn = 200010;
char s1[maxn], s2[maxn];
int len1, len2, cnt[maxn][2];int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);
#endif while (~scanf("%s%s", s1, s2)){len1 = strlen(s1);len2 = strlen(s2);memset(cnt, 0, sizeof(cnt));cnt[0][s2[0] - '0']++;for (int i = 1; i <len2; i++){cnt[i][0] = cnt[i - 1][0] + (s2[i] == '0' ? 1 : 0);cnt[i][1] = cnt[i - 1][1] + (s2[i] == '1' ? 1 : 0);}//cnt[i][0]:在第i个位置之前（包括i)含有字符0的个数,位置从0开始;cnt[i][1]类似long long ans = 0;for (int i = 0; i < len1; i++){if (s1[i] == '0') ans += cnt[len2 - len1 + i][1] - cnt[i][1] + (s2[i] == '1' ? 1 : 0);else ans += cnt[len2 - len1 + i][0] - cnt[i][0] + (s2[i] == '0' ? 1 : 0);}printf("%I64d\n", ans);}return 0;
}