终于肝掉了这道提……

考虑用编辑距离函数处理这个问题。考虑每个可能的结尾\(i\)，定义\(f_i\)（这里把\(*\)看做\(0\)把）：

\[f_i = \sum_{j = 0}^{m - 1} A_j B_{i - m + 1 + j}\,(A_j - B_{i - m + 1 + j})^2\]

考虑翻转\(A\)，式子变成：

\[f_i = \sum_{j = 0}^{m - 1} A_{m - 1 - j}\,B_{i - m + 1 + j}\,(A_j - B_{i - m + 1 + j})^2\]

式子给人一种卷积的即视感……再化简一下，得到：

\[f_i = \sum_{j = 0}^{m - 1} A_{m - 1 - j}^3\,B_{i - m + 1 + j}\,- 2A_{m - 1 - j}^2\,B_{i - m + 1 + j}^2\,+ A_{m - 1 - j}\,B_{i - m + 1 + j}^3\]

这是三个卷积……跑三遍FFT即可得到\(f_i\)，当且仅当\(f_i = 0\)时，以\(i\)结尾的长度为\(m\)的子串才能匹配。

顺便提个几个坑……这个题用long double + std::complex会因为常数巨大而T掉。并且注意eps不要调那么细啊……这个东西精度误差极大，我直接调成1了。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <complex>
constexpr int maxn = 300005;
using R = double;
using C = std::complex<R>;
constexpr R pi = acos(-1);
inline int flip(int bi, int x) {
  int ans = 0;
  for(int i = 0; i < bi; i ++) {
    if(x & (1 << i)) {
      ans += (1 << (bi - i - 1));
    }
  }
  return ans;
}
inline void FFT(C *A, int bi, int n, R flag = 1.00) {
  for(int i = 0; i < n; i ++) {
    int fl = flip(bi, i);
    if(i < fl) std::swap(A[fl], A[i]);
  }
  for(int L = 1; L < n; L <<= 1) {
    R rd = pi / (R(L));
    C xi(cos(rd), sin(flag * rd));
    for(int i = 0; i < n; i += (L << 1)) {
      C w(1.00, 0.00);
      for(int j = i; j < i + L; j ++) {
        C v1 = A[j], v2 = A[j + L];
        A[j] = v1 + v2 * w;
        A[j + L] = v1 - v2 * w;
        w = w * xi;
      }
    }
  }
}

constexpr R eps = 1.00;
inline int sign(R x) {
  if(fabs(x) < eps) {
    return 0;
  } else {
    if(x < 0.00) {
      return -1;
    } else {
      return 1;
    }
  }
}
int main() {
  static char A[maxn], B[maxn];
  static int V1[maxn << 2], V2[maxn << 2];
  static C P1[maxn << 2], P2[maxn << 2], P3[maxn << 2];
  static R F[maxn << 2];
  int m, n; scanf("%d%d", &m, &n);
  if(m > n) {
    puts("0"); return 0;
  }
  scanf("%s%s", A, B);
  std::reverse(A, A + m);
  for(int i = 0; i < m; i ++) {
    V1[i] = (A[i] == '*') ? 0 : (A[i] - 'a' + 1);
  }
  for(int i = 0; i < n; i ++) {
    V2[i] = (B[i] == '*') ? 0 : (B[i] - 'a' + 1);
  }
  int sz = 1, bi = 0;
  while(sz <= (m + n)) {
    sz *= 2; bi ++;
  }
  std::fill(P1, P1 + sz, C(0, 0));
  std::fill(P2, P2 + sz, C(0, 0));
  for(int i = 0; i < m; i ++) {
    P1[i] = V1[i] * V1[i] * V1[i];
  }
  for(int i = 0; i < n; i ++) {
    P2[i] = V2[i];
  }
  FFT(P1, bi, sz); FFT(P2, bi, sz);
  for(int i = 0; i < sz; i ++) {
    P3[i] = P1[i] * P2[i];
  }
  FFT(P3, bi, sz, -1.00);
  for(int i = 0; i < sz; i ++) {
    F[i] += P3[i].real() / (R(sz));
  }
  std::fill(P1, P1 + sz, C(0, 0));
  std::fill(P2, P2 + sz, C(0, 0));
  for(int i = 0; i < m; i ++) {
    P1[i] = V1[i] * V1[i];
  }
  for(int i = 0; i < n; i ++) {
    P2[i] = V2[i] * V2[i];
  }
  FFT(P1, bi, sz); FFT(P2, bi, sz);
  for(int i = 0; i < sz; i ++) {
    P3[i] = P1[i] * P2[i];
  }
  FFT(P3, bi, sz, -1.00);
  for(int i = 0; i < sz; i ++) {
    F[i] += (R(-2)) * P3[i].real() / (R(sz));
  }
  std::fill(P1, P1 + sz, C(0, 0));
  std::fill(P2, P2 + sz, C(0, 0));
  for(int i = 0; i < m; i ++) {
    P1[i] = V1[i];
  }
  for(int i = 0; i < n; i ++) {
    P2[i] = V2[i] * V2[i] * V2[i];
  }
  FFT(P1, bi, sz); FFT(P2, bi, sz);
  for(int i = 0; i < sz; i ++) {
    P3[i] = P1[i] * P2[i];
  }
  FFT(P3, bi, sz, -1.00);
  for(int i = 0; i < sz; i ++) {
    F[i] += P3[i].real() / (R(sz));
  }
  static int ans[maxn]; int cnt = 0;
  for(int i = 0; i < n; i ++) {
#ifdef LOCAL
    printf("F[%d] : %.10Lf\n", i, F[i]);
#endif
    if(sign(F[i]) == 0 && i >= m - 1) {
      ans[cnt ++] = i - m + 1 + 1;
    }
  }
  printf("%d\n", cnt);
  for(int i = 0; i < cnt; i ++) {
    if(i) putchar(' ');
    printf("%d", ans[i]);
  }
  putchar('\n');
  return 0;
}

• 相关文章
• 全局相关文章