题目大意

给定文本串 $S$ 和模式串 $T$，对每个位置进行匹配，得到失配次数。

统计此失配次数，计算前缀和。

分析

我是没料到 HDOJ 没有 M_PI，CE 了几发。

FFT 字符串匹配模板题，我在 ZAFU Wiki 中讲过，即对每个字符卷积。

#include "template/basic/complex.hpp"

const int maxn = 1 << 20;

using img = Complex<double>;
using poly_t = vector<img>;

poly_t w;

#include "template/poly-fft/fft_init.hpp"
#include "template/poly-fft/fft.hpp"

char a[maxn], b[maxn];

int sum[maxn], ans[maxn];

char ch[] = "0123456789*";

int main() {
	w = fft_init(maxn);

	int ttt = rr();
	while (ttt--) {
		int n = rr(), m = rr();
		fill(sum, sum + m + n + 12, 0);
		fill(ans, ans + m + 12, 0);

		int lim = getlim(m, n);

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

		int tsum = 0;
		for (int i = 0; i < m - 1; i++) {
			tsum += b[i] == '*';
			tsum += a[i] == '*';
		}
		tsum += a[m - 1] == '*';

		reverse(a, a + m + 1);
		for (int k = 0; k <= 10; k++) {
			poly_t SS(lim);

			for (int i = 0; i < n; i++)
				SS[i].x = b[i] == ch[k];
			for (int i = 1; i <= m; i++)
				SS[i].y = a[i] == ch[k];

			fft(SS);
			for (int i = 0; i < lim; i++)
				SS[i] = SS[i] * SS[i];
			ifft(SS);

			if (k == 10) {
				for (int i = 0; i <= m + n; i++)
					sum[i] -= int(SS[i].y / 2 + 0.5);
			} else {
				for (int i = 0; i <= m + n; i++)
					sum[i] += int(SS[i].y / 2 + 0.5);
			}
		}
		for (int i = m; i <= n; i++) {
			tsum += (b[i - 1] == '*') - (b[i - m - 1] == '*');
			int tans = tsum + sum[i];
			ans[m - tans]++;
		}
		tsum = 0;
		for (int i = 0; i <= m; i++) {
			tsum += ans[i];
			printf("%d\n", tsum);
		}
	}
	return 0;
}