题意

题目链接

Sol

知道FFT能做字符串匹配的话这就是个裸题了吧。。

考虑把B翻转过来，如果\(\sum_{k = 0}^M (B_{i - k} - A_k)^2 * B_{i-k}*A_k = 0\)

那么说明能匹配。然后拆开三波FFT就行了

/*

*/

#include<bits/stdc++.h>

#define LL long long

const int MAXN = 1e6 + 10, INF = 1e9 + 7;

using namespace std;

inline int read() {

	char c = getchar(); int x = 0, f = 1;

	while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return x * f;

}

int N, M;

LL g[MAXN], f[MAXN];

char sa[MAXN], sb[MAXN];

int ta[MAXN], tb[MAXN], a[MAXN], b[MAXN], rev[MAXN], lim;

LL sqr2(int x) {return 1ll * x * x;}

LL sqr3(int x) {return 1ll * x * x * x;}

const double PI = acos(-1);

struct com {

	double x, y;

	com operator * (const com &rhs) const {

		return {x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x};

	}

	com operator + (const com &rhs) const {

		return {x + rhs.x, y + rhs.y};

	}

	com operator - (const com &rhs) const {

		return {x - rhs.x, y - rhs.y};

	}

}A[MAXN], B[MAXN];

void FFT(com *A, int lim, int type) {

	for(int i = 0; i < lim; i++) if(i < rev[i]) swap(A[i], A[rev[i]]);

	for(int mid = 1; mid < lim; mid <<= 1) {

		com wn = {cos(PI / mid), type * sin(PI / mid)};

		for(int i = 0; i < lim; i += (mid << 1)) {

			com w = {1, 0};

			for(int j = 0; j < mid; j++, w = w * wn) {

				com x = A[i + j], y = w * A[i + j + mid];

				A[i + j] = x + y;

				A[i + j + mid] = x - y;

			}

		}

	}

	if(type == -1) {

		for(int i = 0; i <= lim; i++) A[i].x /= lim;

	}

}

void mul(int *b, int *a) {

	memset(A, 0, sizeof(A)); memset(B, 0, sizeof(B));

	for(int i = 0; i < N; i++) B[i].x = b[i];

	for(int i = 0; i < M; i++) A[i].x = a[i];

	FFT(B, lim, 1);

	FFT(A, lim, 1);

	for(int i = 0; i < lim; i++) B[i] = B[i] * A[i];

	FFT(B, lim, -1);

	for(int i = M - 1; i <= N; i++)

		f[i] += round(B[i].x);

}

signed main() {

	//freopen("2.in", "r", stdin);	freopen("b.out", "w", stdout);

	M = read(); N = read();

	scanf("%s %s", sa, sb);

	for(int i = 0; i < M; i++) ta[i] = (sa[i] == '*' ? 0 : sa[i] - 'a' + 1);

	for(int i = 0; i < N; i++) tb[i] = (sb[i] == '*' ? 0 : sb[i] - 'a' + 1);

	reverse(tb, tb + N);

	int len = 0; lim = 1;

	while(lim <= N + M) len++, lim <<= 1;

	for(int i = 0; i < lim; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << len - 1);

	for(int i = 0; i < N; i++) b[i] = sqr3(tb[i]);

	for(int i = 0; i < M; i++) a[i] = ta[i];

	mul(b, a);

	for(int i = 0; i < N; i++) b[i] = -2 * sqr2(tb[i]);

	for(int i = 0; i < M; i++) a[i] = sqr2(ta[i]);

	mul(b, a);

	for(int i = 0; i < N; i++) b[i] = tb[i];

	for(int i = 0; i < M; i++) a[i] = sqr3(ta[i]);

	mul(b, a);	

	int ans = 0;

	for(int i = M - 1; i < N; i++)

		if(!f[i]) ans++;

	printf("%d\n", ans);

	for(int i = N - 1; i >= M - 1; i--)

		if(!f[i])

			printf("%d ", N - i);

	return 0;

}

/*

3 7

a*b

aebr*ob

*/