Rockdu's Blog

【题目描述】

兔子们在玩两个串的游戏。给定两个字符串S和T，兔子们想知道T在S中出现了几次，分别在哪些位置出现。注意T中可能有“?”字符，这个字符可以匹配任何字符。

【输入】

两行两个字符串，分别代表S和T

【输出】

第一行一个正整数k，表示T在S中出现了几次

接下来k行正整数，分别代表T每次在S中出现的开始位置。按照从小到大的顺序输出，S下标从0开始。

【输入样例】

bbabaababaaaaabaaaaaaaabaaabbbabaaabbabaabbbbabbbbbbabbaabbbababababbbbbbaaabaaabbbbbaabbbaabbbbabab
a?aba?abba

【输出样例】

0

【提示】

S 长度不超过 10^5， T 长度不会超过 S。 S 中只包含小写字母， T中只包含小写字母和“?”

考虑对于每个p位置构造函数，f[p]=(i:0~m-1)(s[p+i]-t[i])^2*t[i]。

如果为'?'那么t[i]为0，否则为ascii码。这样只要f[p]为0，那么以这个位置开头就可以匹配到。现在就是考虑怎么算f[p]，f[p]拆开来是两个乘积加一个三次方。

发现只要我们把s数组反一转就把乘积换成了卷积。

这样变成了卷积形式，可以FFT了。

NTT:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 4e5 + 5;
const int mod = 998244353, G = 3;
const int IG = 332748118;

char s[maxn], t[maxn];
int n, m;
LL sn[maxn << 1], tn[maxn << 1], tmp[maxn << 1];
LL sn2[maxn << 1], tn2[maxn << 1], tn3[maxn << 1];
LL sum, ans[maxn << 1];
LL fpow(LL a, int b) {
	LL ans = 1;
	while(b) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod, b >>= 1;
	}
	return ans;
}

namespace NTT {
	int RL[maxn << 1], N, mxp;
	void init(int n) {
		for(N = 1, mxp = 0; N < n; N <<= 1, ++mxp);
		for(register int i = 1; i <= N; ++i) 
			RL[i] = (RL[i >> 1] >> 1) | ((i & 1) << mxp - 1);
		return ;
	}
	void NTT(LL * A, int type) {
		for(register int i = 0; i < N; ++i)
			if(i < RL[i]) swap(A[i], A[RL[i]]);
		LL Wn, w;
		for(register int i = 1; i < N; i <<= 1) {
			if(~type) Wn = fpow(G, (mod - 1) / (i << 1));
            else Wn = fpow(IG, (mod - 1) / (i << 1));
			for(register int j = 0, p = i << 1; j < N; j += p) {
				w = 1;
				for(register int k = 0; k < i; ++k, w = w * Wn % mod) {
					LL x = A[j + k], y = w * A[j + k + i];
					A[j + k] = (x + y) % mod, A[j + k + i] = (x - y) % mod;
				}
			}
		}
	}
	void mul(LL * A, LL * B, int n, int m) {
		init(n + m);
		NTT(A, 1), NTT(B, 1);
		for(register int i = 0; i <= N; ++i)
			A[i] = A[i] * B[i] % mod;
		NTT(A, -1);
		LL inv = fpow(N, mod - 2);
		for(register int i = 0; i <= N; ++i)
			A[i] = A[i] * inv % mod, A[i] = (A[i] + mod) % mod;
	}
}

int main() {
	scanf("%s", s), scanf("%s", t);
	n = strlen(s) - 1, m = strlen(t) - 1;
	int u;
	for(register int i = 0; i <= n; ++i) {
		u = n + m - i;
		sn[u] = (int)s[i], sn2[u] = sn[u] * sn[u] % mod;
	}
	for(register int i = 0; i <= m; ++i) {
		if(t[i] == '?') tn[i] = 0;
		else tn[i] = (int)t[i];
		tn2[i] = tn[i] * tn[i] % mod;
		tn3[i] = tn[i] * tn2[i] % mod;
		sum += tn3[i], sum %= mod;
	}
	memcpy(tmp, tn2, sizeof(tn2));
	NTT::mul(sn, tmp, n + m + 1, n + m + 1);
	reverse(sn, sn + n + m + 1);
	memcpy(tmp, tn, sizeof(tn));
	NTT::mul(sn2, tmp, n + m + 1, n + m + 1);
	reverse(sn2, sn2 + n + m + 1);
	int cnt = 0;
	for(register int i = 0; i <= n - m; ++i) {
		ans[i] = sn2[i] - 2 * sn[i] + sum;
		if(!ans[i]) ++cnt;
	}
	if(!cnt) return printf("0"), 0;
	else printf("%d\n", cnt);
	for(register int i = 0; i <= n - m; ++i) {
		if(!ans[i]) printf("%d\n", i);
	}
	return 0;
}

FFT:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<complex>
#define E complex<double >
#define eps 1e-10
using namespace std;
const int maxn = 4e5 + 5;
const double Pi = acos(-1);
char s[maxn], t[maxn];
int n, m;
E sn[maxn << 1], tn[maxn << 1], tmp[maxn << 1];
E sn2[maxn << 1], tn2[maxn << 1], tn3[maxn << 1];
int ans[maxn << 1];
double sum;

namespace FFT {
	int RL[maxn << 1], N, mxp;
	void init(int n) {
		for(N = 1, mxp = 0; N < n; N <<= 1, ++mxp);
		for(register int i = 1; i <= N; ++i) 
			RL[i] = (RL[i >> 1] >> 1) | ((i & 1) << mxp - 1);
		return ;
	}
	void FFT(E * A, int type) {
		for(register int i = 0; i < N; ++i)
			if(i < RL[i]) swap(A[i], A[RL[i]]);
		E Wn, w;
		for(register int i = 1; i < N; i <<= 1) {
			Wn = E(cos(Pi / i), sin(Pi / i) * type);
			for(register int j = 0, p = i << 1; j < N; j += p) {
				w = E(1, 0);
				for(register int k = 0; k < i; ++k, w = w * Wn) {
					E x = A[j + k], y = w * A[j + k + i];
					A[j + k] = (x + y), A[j + k + i] = (x - y);
				}
			}
		}
	}
	void mul(E * A, E * B, int n, int m) {
		init(n + m);
		FFT(A, 1), FFT(B, 1);
		for(register int i = 0; i <= N; ++i)
			A[i] = A[i] * B[i];
		FFT(A, -1);
		for(register int i = 0; i <= N; ++i)
			A[i].real() /= N;
	}
}

int main() {
	//freopen("test.txt", "r", stdin);
	scanf("%s", s), scanf("%s", t);
	n = strlen(s) - 1, m = strlen(t) - 1;
	int u;
	for(register int i = 0; i <= n; ++i) {
		u = n + m - i;
		sn[u].real() = s[i] - 'a' + 1, sn2[u] = sn[u] * sn[u];
	}
	for(register int i = 0; i <= m; ++i) {
		if(t[i] == '?') tn[i] = 0;
		else tn[i].real() = t[i] - 'a' + 1;
		tn2[i] = tn[i] * tn[i];
		tn3[i] = tn[i] * tn2[i];
		sum += tn3[i].real();
	}
	memcpy(tmp, tn2, sizeof(tn2));
	FFT::mul(sn, tmp, n + m + 1, n + m + 1);
	reverse(sn, sn + n + m + 1);
	for(register int i = 0; i < n + m; ++i)
		sn[i].real() = (int)(sn[i].real() + 0.5), sn[i].imag() = 0;
	memcpy(tmp, tn, sizeof(tn));
	FFT::mul(sn2, tmp, n + m + 1, n + m + 1);
	reverse(sn2, sn2 + n + m + 1);
	int cnt = 0;
	for(register int i = 0; i < n + m; ++i)
		sn2[i].real() = (int)(sn2[i].real() + 0.5), sn2[i].imag() = 0;
	for(register int i = 0; i <= n - m; ++i) {
		ans[i] = (int)(sn2[i].real() - 2 * sn[i].real() + sum + 0.5);
		if(!ans[i]) ++cnt;
	}
	if(!cnt) return printf("0"), 0;
	else printf("%d\n", cnt);
	for(register int i = 0; i <= n - m; ++i) {
		if(!ans[i]) printf("%d\n", i);
	}
	return 0;
}