AcWing 831. KMP字符串——FFT解法 $O(n\log n)$    原题链接    简单

作者： 作者的头像   垫底抽风 ,  2020-08-24 09:51:19 ,  所有人可见 ,  阅读 5197

34


18

为了用FFT过这题我还专门让y总把这题空间限制调大了

FFT 在字符串匹配中的应用

先修知识：FFT{:target=”_blank”}

对于给定的两个字符串 $s[m], p[n]$，

我们可以定义匹配函数 $c(i, j) = s[i] - p[j]$

再定义完全匹配函数 $ C(x) = \begin {aligned} \sum _ {i = 0} ^ {n - 1} c(x + i, i) \end {aligned} $

那么如果 $s[x \sim x + n - i]$ 与 $p$ 完全匹配，则 $C(x) = 0$

但是我们可以只通过 $C(x)$ 是否为 $0$，直接判断 $s[x ~ x + n - i]$ 与 $p$ 是否完全匹配吗？

用完全匹配函数判断一下 abc 和 cba 试试？

似乎在我们的定义下，abc 和 cba 是匹配的？

匹配函数没错，如果两个字符不同，一定会返回一个非零值

所以问题出在了我们的完全匹配函数上

在我们的定义下，只要两个字符串所包含的字符集合是相同的，不管排列如何，完全匹配函数都会返回 $0$

（当然，两个字符串所包含的字符集合不同，完全匹配函数也是有可能返回 $0$ 的，比如 add 和 ccc 也是匹配的）

我们的完全匹配函数，直接将所有匹配函数的结果相加，而没有考虑正负号

对于判定正负号，我们可以给匹配函数，直接暴力地加一个绝对值上去

但是这样就只能 $O(nm)$ 暴力算了

不难想到，我们可以将匹配函数，变为 $c(i, j) = (s[i] - p[j]) ^ 2$

这样就不会出问题了，但是会难算一些

先将其代入完全匹配函数

$$ C(x) = \begin {aligned} \sum _ {i = 0} ^ {n - 1} (s[x + i] - p[i]) ^ 2 \end {aligned} $$

将平方展开

$$ C(x) = \begin {aligned} \sum _ {i = 0} ^ {n - 1} (s[x + i] ^ 2 + p[i] ^ 2 - 2 s[x + i] p[i]) \end {aligned} $$

再将求和展开

$$ C(x) = \begin {aligned} \sum _ {i = 0} ^ {n - 1} s[x + i] ^ 2 + \sum _ {i = 0} ^ {n - 1} p[i] ^ 2 - 2 \sum _ {i = 0} ^ {n - 1} s[x + i] p[i] \end {aligned} $$

对于第一项，我们可以用前缀和处理；

对于第二项，是一个常数，可以预处理出来；

所以我们剩下要考虑的，就是如何快速求出第三项

$$ \begin {aligned} \sum _ {i = 0} ^ {n - 1} s[x + i] p[i] \end {aligned} $$

这么看确实没什么思路，我们令 $j = n - i - 1$ 并将其代入，得

$$ \begin {aligned} \sum _ {i + j = n - 1, 0 \leq i < n} s[x + i] p[n - j - 1] \end {aligned} $$

然后我们可以将 $p$ 翻转，那么就有

$$ \begin {aligned} \sum _ {i + j = n - 1, 0 \leq j < n} s[x + i] p[j] \end {aligned} $$

也就是

$$ \begin {aligned} \sum _ {i + j = n + x - 1, 0 \leq j < n} s[i] p[j] \end {aligned} $$

这不就是我们熟悉的卷积形式了吗

那么我们就可以用 $\text{FFT}$ 解决掉这项了

我们也就可以用 $O(n \log n)$ 的复杂度，求出所有的 $C$ 函数的值了

时间复杂度

时间复杂度的瓶颈在 FFT 上，为 $O(n \log n)$

参考文献

浅谈 FFT (1){:target=”_blank”}
浅谈 FFT (2){:target=”_blank”}

C ++ 代码

#include <cmath>
#include <cstdio>

// 前缀和有可能爆 int
typedef long long ll;

struct cp
{
    double a, b;
    cp(double x = 0, double y = 0) {a = x, b = y;}
    cp operator + (const cp &t) const {return cp(a + t.a, b + t.b);}
    cp operator - (const cp &t) const {return cp(a - t.a, b - t.b);}
    cp operator * (const cp &t) const {return cp(a * t.a - b * t.b, a * t.b + b * t.a);}
};

int log_2(int x)
{
    int res = 0;
    if (x & 0xffff0000) res += 16, x >>= 16;
    if (x & 0xff00) res += 8, x >>= 8;
    if (x & 0xf0) res += 4, x >>= 4;
    if (x & 0xc) res += 2, x >>= 2;
    if (x & 2) res ++ ;
    return res;
}

void swap(cp &a, cp &b)
{
    static cp t;
    t = a, a = b, b = t;
}

const int N = 100005;
const int M = 4000005;
const double pi = 2 * acos(-1);

int n, m, k;
int r[M], c[M];  // c 即最后求出来的 C 函数
char s[N], p[M];
ll sum, f[M];    // sum 用于预处理上面 C 函数中第二项的值。f 用于预处理 C 函数第一项的值。
cp a[M], w[M];

void init()
{
    k = n + m - 2;
    int bit = log_2(k);
    k = 1 << bit + 1;
    for (int i = 0; i < k; i ++ ) r[i] = r[i >> 1] >> 1 | (i & 1) << bit;
    const cp t(cos(pi / k), sin(pi / k)); (*w).a = 1;
    for (int i = 1; i < k; i ++ ) w[i] = w[i - 1] * t;
}

void FFT(bool type)
{
    for (int i = 0; i < k; i ++ ) if (i < r[i]) swap(a[i], a[r[i]]);
    static cp x, y;
    for (int len = 2; len <= k; len <<= 1)
        for (int l = 0; l < k; l += len)
            for (int i = 0, j = len >> 1; j < len; i ++ , j ++ )
            {
                x = a[l + i], y = w[k / len * i];
                if (type) y = y * a[l + j];
                else    y = cp(y.a, -y.b) * a[l + j];
                a[l + i] = x + y, a[l + j] = x - y;
            }
}

int main()
{
    scanf("%d\n%s\n%d\n%s", &n, p, &m, s);

    // 预处理 sum 和 f
    for (int i = 0; i < n; i ++ ) sum += p[i] * 1ll * p[i];
    for (int i = 1; i <= m; i ++ ) f[i] = f[i - 1] + s[i - 1] * 1ll * s[i - 1];

    // 将 s 和 p 放到 a 中做 FFT，其中 p 要反着放
    for (int i = 0; i < n; i ++ ) a[i].a = p[n - i - 1];
    for (int i = 0; i < m; i ++ ) a[i].b = s[i];

    // 一顿 FFT
    init();
    FFT(1);
    for (int i = 0; i < k; i ++ ) a[i] = a[i] * a[i];
    FFT(0);

    // 求出 c
    for (int i = 1; i < n + m; i ++ ) c[i] = (int) (a[i - 1].b / k / 2.0 + 0.5);
    for (int i = n; i <= m; i ++ )
        // 如果 C(i) 为 0，则输出 i - n
        if (f[i] - f[i - n] + sum - 2 * c[i] == 0)
            printf("%d ", i - n);

    return 0;
}

很不幸，最后一个点 $\text{TLE}$ 了。。

但是如果你是卡常数带师，应该也可以卡常过掉这题

加火车头 AC 代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

#include <cmath>
#include <cstdio>

typedef long long ll;

struct cp
{
    double a, b;
    inline cp(double x = 0, double y = 0) {a = x, b = y;}
    inline cp operator + (const cp &t) const {return cp(a + t.a, b + t.b);}
    inline cp operator - (const cp &t) const {return cp(a - t.a, b - t.b);}
    inline cp operator * (const cp &t) const {return cp(a * t.a - b * t.b, a * t.b + b * t.a);}
};

inline int log_2(register int x)
{
    int res = 0;
    if (x & 0xffff0000) res += 16, x >>= 16;
    if (x & 0xff00) res += 8, x >>= 8;
    if (x & 0xf0) res += 4, x >>= 4;
    if (x & 0xc) res += 2, x >>= 2;
    if (x & 2) res ++ ;
    return res;
}

inline void swap(cp &a, cp &b)
{
    static cp t;
    t = a, a = b, b = t;
}

const int N = 100005, M = 4000005;
const double pi = 2 * acos(-1);

int n, m, k;
int r[M];
char s[M >> 2], p[N];
ll sum, f[M >> 2];
cp a[M], w[M];

inline void init()
{
    k = n + m - 2;
    register int bit = log_2(k), *i, *j;
    for (i = j = r, k = 1 << bit + 1, bit = k >> 1; i < r + k; i += 2, j ++ )
        *(i + 1) = (*i = *j >> 1) | bit;
    cp t(cos(pi / k), sin(pi / k)), *pt; (*w).a = 1;
    for (pt = w + 1; pt < w + k; pt ++ ) *pt = *(pt - 1) * t;
}

inline void FFT(bool type)
{
    register int i, len, l;
    for (i = 0; i < k; i ++ ) if (i > r[i]) swap(a[i], a[r[i]]);
    static cp *x, *y, v;
    for (len = 2; len <= k; len <<= 1)
        for (l = 0; l < k; l += len)
            for (i = len >> 1, x = a + l, y = x + i; i < len; x ++ , y ++ , i ++ )
            {
                v = w[k / len * (i - (len >> 1))];
                if (type) v.b = -v.b;
                v = v * *y;
                *y = *x - v, *x = *x + v;
            }
}

int main()
{
    scanf("%d\n%s\n%d\n%s", &n, p, &m, s);
    for (int i = 0; i < n; i ++ ) p[i] -= 96;
    for (int i = 0; i < m; i ++ ) s[i] -= 96;
    register char *c; register ll *it, *jt; cp *pt;
    for (c = p; *c; c ++ ) sum += *c * 1ll * *c;
    for (it = f, c = s; *c; c ++ , it ++ ) *(it + 1) = *it + *c * 1ll * *c;
    for (pt = a, c = p + n - 1; c >= p; c -- , pt ++ ) pt->a = *c;
    for (pt = a, c = s; *c; c ++ , pt ++ ) pt->b = *c;
    init();
    FFT(0);
    for (pt = a; pt < a + k; pt ++ ) *pt = *pt * *pt;
    FFT(1);
    k <<= 1;
    for (pt = a + n - 1, it = f + n, jt = f; it <= f + m; pt ++ , it ++ , jt ++ )
        if (((ll) (pt->b / k + 0.5)) << 1 == *it - *jt + sum)
            printf("%d ", it - f - n);
    return 0;
}

$$ $$

$\text{Update: NTT Code}$

#pragma GCC optimize(2)
#include <stdio.h>
#include <string.h>

typedef long long LL;
const int N = 100005, M = 1000005;
const int mod = 998244353, G = 3;

void bmod(int &x) {
  x += x >> 31 & mod;
}
void Add(int &x, int y) {
  x += y - mod, x += x >> 31 & mod;
}
void swap(int &x, int &y) {
  x ^= y ^= x ^= y;
}
void reverse(int *st, int *ed) {
  while (st < --ed) swap(*st++, *ed);
}
int inv(int x, int k = mod - 2) {
  int r = 1;
  while (k) {
    if (k & 1) r = (LL)x * r % mod;
    x = (LL)x * x % mod;
    k >>= 1;
  }
  return r;
}

int n, m;
char s[M], p[N];
int v[M], w;

const int R = 2200005;

int f[R], g[R];
int lim, rt[R], rev[R];
void prework(int n) {
  lim = 1;
  while (lim < n) lim <<= 1;
  for (int i = 1; i < lim; ++i) {
    rev[i] = rev[i >> 1] >> 1 | (i & 1 ? lim >> 1 : 0);
  }
  for (int k = 2, i; k <= lim; k <<= 1) {
    rt[i = k >> 1] = 1;
    LL v = inv(G, (mod - 1) / k);
    for (int j = i + 1; j < k; ++j) {
      rt[j] = rt[j - 1] * v % mod;
    }
  }
}
void NTT(int *f, bool flag = true) {
  if (!flag) reverse(f + 1, f + lim);
  for (int i = 0; i < lim; ++i) {
    if (i < rev[i]) {
      swap(f[i], f[rev[i]]);
    }
  }
  for (int k = 2; k <= lim; k <<= 1) {
    for (int i = 0, len = k >> 1; i < lim; i += k) {
      for (int j = i, *bf = rt + len, x; j < i + len; ++j, ++bf) {
        x = f[len + j] * (LL)*bf % mod;
        bmod(f[len + j] = f[j] - x);
        bmod(f[j] += x - mod);
      }
    }
  }
  if (flag) return;
  LL v = inv(lim);
  for (int i = 0; i < lim; ++i) {
    f[i] = f[i] * v % mod;
  }
}

int main() {
  scanf("%d%s%d%s", &n, p + 1, &m, s + 1);
  for (int i = 1; i <= m; ++i) {
    bmod(v[i] = v[i - 1] + (s[i] * (int) s[i]) - mod);
  }
  for (int i = 1; i <= n; ++i) {
    Add(w, p[i] * (int) p[i]);
  }
  for (int i = 0; i < m; ++i) {
    f[i] = s[i + 1];
  }
  for (int i = 0; i < n; ++i) {
    g[i] = p[n - i];
  }
  prework(n + m - 1);
  NTT(f), NTT(g);
  for (int i = 0; i < lim; ++i) {
    f[i] = f[i] * (LL)g[i] % mod;
  }
  NTT(f, false);
  for (int i = n; i <= m; ++i) {
    if ((v[i] - (LL)v[i - n] + w - 2 * f[i - 1]) % mod == 0) {
      printf("%d ", i - n);
    }
  }
  return 0;
}

13 评论

用户头像
chstor   2020-08-24 10:59      2    踩      回复

佬，火车头什么作用呀？

用户头像
垫底抽风   2020-08-24 11:10      2    踩      回复

就是让编译器帮你给代码卡个常，具体内容问百度吧，我也不是很清楚

用户头像
chstor   2020-08-24 16:01    回复了 垫底抽风 的评论      2    踩      回复

嗯嗯，好

用户头像
心里没有一点AC数   2020-08-24 18:59      1    踩      回复

再推荐你学一点黑科技，比如 surreal number 应对不平等博弈。。。
这个算法的发明者conway 因为新冠肺炎，离世了。。

用户头像
垫底抽风   2020-08-24 21:12         踩      回复

啊那个好难QAQ，期待您的文章%%%

用户头像
胡图图   2020-08-24 10:13      1    踩      回复

后浪！

用户头像
垫底抽风   2020-08-24 10:21      2    踩      回复

这个就是我第二篇FFT分享里面的一段，单独拿了出来

用户头像
Link_Cut_Y   2023-01-05 08:23         踩      回复

%%%%

用户头像
Leo_3   2021-07-16 20:43         踩      回复

有意思

用户头像
div   2020-10-01 19:26         踩      回复

FFT点进去竟然有傅里叶变换?这是我第一次编程中发现大学的有些知识

用户头像
垫底抽风   2020-10-01 20:23         踩      回复

$\text{FFT}$ 即 $\text{Fast Fourier Transform}$，快速傅里叶变换

用户头像
图灵酱   2023-10-24 21:43    回复了 垫底抽风 的评论         踩      回复

等等，佬你现在多大了啊

用户头像
心里没有一点AC数   2020-08-24 18:32         踩      回复

O......Orz
%%%%%%%
%%%%%%%