字典树

字符串的异或结果为0，则其串中1的个数必为偶数。

对于$A$中的每个长度为$n$的子串，需要判断该串是否出现过，可以使用哈希来判重，也可以将所有子串扔到字典树(Trie)树上，这样树上从根节点到叶节点的每一条路径，都是独一无二的。

在添加进Trie树时，统计1的个数并进行答案统计即可。

在获取所有子串时，需要对比$A$和$B$。

所以，时间复杂度为$O(nm)$

代码

C++

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int maxn=5e3+10;
int m,n;
char a[maxn<<1],b[maxn];
int ans=0;

struct node{
	node *lson,*rson;
	node(){
		lson = nullptr;
		rson = nullptr;
	}
};

node *root;

void add(int x){
	node *p = root;
	int cnt=0;
	bool flag=false;
	for(int i=0;i<n;++i){
		if(a[i+x]==b[i+1]){
			if(p->lson==nullptr){
				p->lson = new node;
				flag=true;
			}
			p=p->lson;
		}else{
			if(p->rson==nullptr){
				p->rson = new node;
				flag=true;
			}
			p=p->rson;
			cnt++;
		}
	}
	ans += !(cnt&1)&&flag;
}

int main(){
    scanf("%d %d",&m,&n);
    scanf("%s",a+1);
    scanf("%s",b+1);
    root = new node;
	for(int i=1;i<=m-n+1;++i){
    	add(i);
	}
    printf("%d",ans);
    
    return 0;
}

python

"""
要求1的个数为偶数，sum(s)=0

"""
m,n=map(int,input().split())
a=input()
b=input()
res = set()
for i in range(0,m-n+1):
    tmp_a=a[i:i+n]
    s = bin(int(tmp_a,2)^int(b,2))[2:]
    count = 0
    for c in s:
        if c=='1':
            count +=1
    if count %2==0:
        res.add(tmp_a)
print(len(res))

java

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        in.nextLine();
        String A = in.nextLine();
        String B = in.nextLine();
        Set<String> hashSet = new HashSet<>();
        //选择下标i;
        for (int i = 0; i <= m-n; i++) {
            //获取字串
            String subStr = A.substring(i,n+i); // e.g 10
            // 将字串各字符与B个字符进行异或运算;
            StringBuilder sb = new StringBuilder();
            // 检查是否valid;
            int valid = 0;
            for (int j = 0; j < n; j++) {
                int num = B.charAt(j) ^ subStr.charAt(j);
                valid ^= num;
                sb.append(num);
            }
            if (valid == 0){
                hashSet.add(sb.toString());
            }
        }
        System.out.println(hashSet.size());
    }
}

题目描述

$\qquad$小红拥有两个仅由0和1组成的字符串A，B，其中A的长度为$m$，B的长度为$n$，字符串下标都从$0$开始。现在小红定义了一种字符串生成模式：

$\qquad$（1）从字符串A中选择一个下标$i$，其中$0 \le i \le m-n$；

$\qquad$（2）从下标$i$开始，获取字符串A一个长度为$n$的连续子串；

$\qquad$（3）将取出的子串各字符依次与字符串B中各字符作异或运算，最终生成一个字符串。

$\qquad$例如，字符串A为10101，字符串B为01，则当$i=0$时，生成的字符串为$11$。当$i=1$时，生成的字符串为$00$。

$\qquad$现在定义生成的字符串合法条件为，当且仅当生成的字符串各个字符异或的结果为$0$，更正规的，假设合法的生成的字符串为$S$，S的长度恒等于$n$，对于所有$0 \le i \lt n$，有S[0]^S[1]^...^S[n-1]=0。比如上面的例子中，生成的两个字符串都是合法的。

$\qquad$现在小红想问你，对于给定的字符串A和B，一共有多少种不同的子串可以生成合法的串？

$\qquad$定义两个字符串不同，当对两个串相同下标对应的字符不同，即为字符串不同，例如字符串$10$和$01$不相同。

输入描述

$\qquad$第一行输入两个整数$m$和$n$，分别表示字符串A和B的长度。其中$1 \le n \le m \le 5000$

$\qquad$第二行输入字符串A，第三行输入字符串B。

输出描述

$\qquad$输出一个整数，表示不同的子串个数。

样例

输入

8 2
10100000
01

输出

2

输出解释

用子串10和01生成串合法串11和00，两个用于生成的子串10和01互不相同，所以结果为2。

Limitation

1s, 1024KiB for each test case.