题意 ： 给你两个只包含 0 和 1 的字符串 a, b，定义函数 f ( A, B ) 为 字符串A和字符串B 比较
存在多少个位置 i 使得 A[ i ] != B[ i ] ，例如
- f(00110,01100)=2
- f(00110,11000)=4
- f(00110,10001)=4
- f(00110,00010)=1
问你 取出 a 中 所有 长度 为 lenb （字符串b的长度） 的子串 c， 求 f ( c, b) 为偶数的 c 的个数。
解 ： 显然， a 中 存在 lena - lenb + 1 个 c， 直接枚举显然是爆的， 字符串只包含 0 1 且 题目只问 f ( b, c ) 的奇偶性。
想到异或，若 在位置 i 上 b[ i ] != c[ i ]， 则 b[ i ] ^ c[ i ] = 1； 否则 b[ i ] ^ c[ i ] = 0；
所以可以 用 一个 ans 来记录 f ( b, c) 的奇偶性， 那么只要枚举 b字符串的长度，然后 ans = ans ^ b[ i ] ^ c[ i ] 就行了
最后判断一下 ans 的奇偶性看满不满足就行了。
这题的关键是 a 的 长度为 lenb 的子串 c 有很多， 你不可能对于每个 c 都去遍历一遍 b字符串。
首先，枚举a 的所有长度为 lenb 的子串 c 枚举 i , 字符串 c 就是 a[ i ] ~ a[ i + lenb - 1]；
首先，先取第一个 c ; a[ 0 ] ~ a[ lenb - 1] 与 b 进行比较 求出 ans0；
然后 对于 第二个 c ： a[ 1 ] ~ a[ lenb ] 的 ans1 就会等于 ans0 ^ a[ 0 ] ^ a[ lenb ]；
同理 对于 第 i 个 c： a[ i ] ~ a[ i + lenb - 1 ] 的 ans( i ) = ans( i - 1 ) ^ a[ i - 1 ] ^ a[ i + lenb - 1]
为什么可以这样写呢； 那就是 因为异或的性质啦。 异或 a [ i - 1 ] 是消除 a[ i - 1 ] 的影响
异或 a [ i + lenb - 1] 是加入计算；
举个例： 现在令 a = 01100010 ; b = 00110；
第一个 c 的 ans 是
（ 0 ^ 0 ）^（ 1 ^ 0 ）^（ 1 ^ 1 ）^（ 0 ^ 1 ）^（ 0 ^ 0 ）
第二个 c 的 ans
（ 0 ^ 0 ）^（ 1 ^ 0 ）^（ 1 ^ 1 ）^（ 0 ^ 1 ）^（ 0 ^ 0 ）^ 0 ^ 0 // 第一个0 是a[ i - 1 ],第二个0是a[ i + lenb - 1 ]；
= 0 ^ （ 0 ^ 0 ）^（ 1 ^ 0 ）^（ 1 ^ 1 ）^（ 0 ^ 1 ）^（ 0 ^ 0 ）^ 0 // 异或两次相当于没有异或
= （ 0 ^ 1）^（ 0 ^ 1 ）^（ 1 ^ 0 ）^（ 1 ^ 0 ）^（ 0 ^ 0 ）
用到了 异或 运算 的 交换律 和 异或两次等于没异或的性质。 挺巧妙的这个思维。
代码里 的 i 和我说的 i 不一样，不过道理都是一样的啦；
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define LL long long
#define ULL unsigned long long
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define dep(i,j,k) for(int i=k;i>=j;i--)
#define INF 0x3f3f3f3f
#define mem(i,j) memset(i,j,sizeof(i))
#define make(i,j) make_pair(i,j)
#define pb push_back
#define Pi acos(-1.0)
using namespace std;
const int N = ;
int main() {
string a, b;
cin >> a >> b;
int ans = , coun = ;
int lena = a.size(); int lenb = b.size();
rep(i, , lenb - ) ans = ans ^ ( a[i] - '') ^ (b[i] - '');
if(ans % == ) coun++;
rep(i, lenb, lena - ) {
ans = ans ^ (a[i - lenb] - '') ^ (a[i] - '');
if(ans % == ) coun++;
}
cout << coun << endl;
return ;
}