CodeForces - 1186 C. Vus the Cossack and Strings (异或)

Vus the Cossack has two binary strings, that is, strings that consist only of "0" and "1". We call these strings aa and bb. It is known that |b|≤|a||b|≤|a|, that is, the length of bb is at most the length of aa.

The Cossack considers every substring of length |b||b| in string aa. Let's call this substring cc. He matches the corresponding characters in bband cc, after which he counts the number of positions where the two strings are different. We call this function f(b,c)f(b,c).

For example, let b=00110b=00110, and c=11000c=11000. In these strings, the first, second, third and fourth positions are different.

Vus the Cossack counts the number of such substrings cc such that f(b,c)f(b,c) is even.

For example, let a=01100010a=01100010 and b=00110b=00110. aa has four substrings of the length |b||b|: 0110001100, 1100011000, 1000110001, 0001000010.

f(00110,01100)=2f(00110,01100)=2;
f(00110,11000)=4f(00110,11000)=4;
f(00110,10001)=4f(00110,10001)=4;
f(00110,00010)=1f(00110,00010)=1.

Since in three substrings, f(b,c)f(b,c) is even, the answer is 33.

Vus can not find the answer for big strings. That is why he is asking you to help him.

Input

The first line contains a binary string aa (1≤|a|≤1061≤|a|≤106) — the first string.

The second line contains a binary string bb (1≤|b|≤|a|1≤|b|≤|a|) — the second string.

Output

Print one number — the answer.

Examples

input

Copy

01100010

00110

output

Copy

input

Copy

1010111110

0110

output

Copy

题意：

给出一个01字符串a,一个01字符串b,将a中每一个长度和b相等的子串取出，问有多少个子串，和b对应位置上数字不同的个数是偶数。

思路：

使用异或运算即可。

充分利用异或可交换的性质。

#include<iostream>

#include<algorithm>

#include<vector>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<ctime>

#define fuck(x) cout<<#x<<" = "<<x<<endl;

#define debug(a, x) cout<<#a<<"["<<x<<"] = "<<a[x]<<endl;

#define ls (t<<1)

#define rs ((t<<1)|1)

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn = ;

const int maxm = ;

const int inf = 0x3f3f3f3f;

const ll Inf = ;

const int mod = ;

const double eps = 1e-;

const double pi = acos(-);

char a[maxn],b[maxn];

int main() {

//    ios::sync_with_stdio(false);

//    freopen("in.txt", "r", stdin);

    scanf("%s%s",a,b);

    int lena = strlen(a);

    int lenb = strlen(b);

    int ans=;

    for(int i=;i<lenb;i++){

        ans^=(a[i]-)^(b[i]-);

    }

    int sum=;

    if(!ans){sum++;}

    for(int i=lenb;i<lena;i++){

        ans^=(a[i]-)^(a[i-lenb]-);

        if(!ans){sum++;}

    }

    printf("%d",sum);

    return ;

}

巴特西

CodeForces - 1186 C. Vus the Cossack and Strings (异或)

最新文章

热门文章