HDU

题目大意 给定文本串 $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]....