FFT

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

typedef long double ld;
const int N = 9000000;
const ld pi = acos(-1);
struct CP {
    ld x, y;
    CP operator+(const CP& a) const {return {x + a.x, y + a.y};}
    CP operator-(const CP& a) const {return {x - a.x, y - a.y};}
    CP operator*(const CP& a) const {return {x * a.x - y * a.y, x * a.y + y * a.x};}
}a[N], b[N];
int rev[N],limit, len, n, m;
void fft(CP a[], int inv) {
    for (int i = 0;i < limit; i ++) 
        if (i < rev[i]) {
            swap(a[i], a[rev[i]]);
            //
        }
    for (int mid=  1; mid < limit;mid <<= 1) {
        auto w1 = CP({(ld)cos(pi/mid), (ld)inv * (ld)sin(pi/(ld)mid)});
        //cout << mid << ":";
        for (int i = 0; i < limit; i += mid * 2) {
            auto wk = CP({1, 0});
            for (int j = 0; j < mid; j ++, wk = wk * w1) {
                auto x = a[i + j], y = wk * a[i + j + mid];
                a[i + j] = x + y;
                a[i + j + mid] = x-y;
                
            }
        }
    }
}
char s1[N], s2[N];
ll sum[N];
void clear() {
    for (int i = 0; i < limit; i++) {
        a[i] = CP({0, 0});
        b[i] = CP({0, 0});
        sum[i] = 0;
    }
    len = 0;
    limit = 0;
}
void solve() {
    while (cin >> (s1) >> s2) {
        n = strlen(s1);
        m = strlen(s2);
        reverse(s1, s1 + n);
        reverse(s2, s2 + m);
        n--,m--;
        len = 0;
        for (int i = n; i >= 0; i --)a[i].x = s1[i] - '0';//, cout << a[i].x;cout << endl;
        for (int i = m; i >= 0; i --)b[i].x = s2[i] - '0';//, cout << b[i].x;cout << endl;
        while ((1 << len) < n + m + 1)len++;
        limit = 1<<len;
        for (int i = 0; i < limit; i ++)     rev[i] = (rev[i >> 1]>>1)|((i&1)<<(len-1));
        fft(a, 1), fft(b, 1);
        for (int i = 0; i < limit; i ++) a[i] = a[i] * b[i];
        fft(a, -1);
        int t = n + m;
        for (int i = 0; i <=n + m || sum[i] != 0 ; i ++) {
            int x = (int)(a[i].x / limit + 0.5);
            sum[i] += x;
            sum[i + 1] += sum[i]/10;
            sum[i] %= 10;
            t = i;
        }
        bool f = 1;
        bool co = 0;
        for (int i = t; i  >= 0; i --) {
            if (f && sum[i] ==0)continue;
            f = 0;
            cout << sum[i];
        }
        if (f)cout << 0;
        cout << endl;
        clear();
    }
}
signed main() {
   ll t = 1;//cin >> t;
   while (t--) {
      solve();
   }
}

字符串模糊匹配

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

typedef double ld;
const int N = 2e6;
const ld pi = acos(-1);
struct CP {
    ld x, y;
    CP operator+(const CP& a) const { return {x + a.x, y + a.y}; }
    CP operator-(const CP& a) const { return {x - a.x, y - a.y}; }
    CP operator*(const CP& a) const {
        return {x * a.x - y * a.y, x * a.y + y * a.x};
    }
} a[N], b[N], f[N], g[N], ans[N];
int rev[N], limit, len, n, m;
void fft(CP a[], int inv) {
    for (int i = 0; i < limit; i++)
        if (i < rev[i]) {
            swap(a[i], a[rev[i]]);
            //
        }
    for (int mid = 1; mid < limit; mid <<= 1) {
        auto w1 = CP({(ld)cos(pi / mid), (ld)inv * (ld)sin(pi / (ld)mid)});
        // cout << mid << ":";
        for (int i = 0; i < limit; i += mid << 1) {
            auto wk = CP({1, 0});
            for (int j = 0; j < mid; j++, wk = wk * w1) {
                auto x = a[i + j], y = wk * a[i + j + mid];
                a[i + j] = x + y;
                a[i + j + mid] = x - y;
            }
        }
    }
}
char s1[N], s2[N];
void clear() {
    for (int i = 0; i < limit; i++) {
        a[i] = CP({0, 0});
        b[i] = CP({0, 0});
        // sum[i] = 0;
    }
    len = 0;
    limit = 0;
}
void solve() {
    ios::sync_with_stdio(0);
    while (cin >> n >> m) {
        cin >> s1 >> s2;
        reverse(s1, s1 + n);

        n--, m--;
        len = 0;
        for (int i = 0; i <= n; i++)
            a[i].x =
                (s1[i] == '*')
                    ? 0
                    : (s1[i] - 'a' + 1);  //, cout << (char)a[i].x;cout << endl;
        for (int i = 0; i <= m; i++)
            b[i].x =
                (s2[i] == '*')
                    ? 0
                    : (s2[i] - 'a' + 1);  //, cout << (char)b[i].x;cout << endl;
        while ((1 << len) < n + m + 1) len++;
        limit = 1 << len;

        for (int i = 0; i < limit; i++)
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (len - 1));

        for (int i = 0; i < limit; i++)
            f[i] = CP({a[i].x * a[i].x * a[i].x, 0}), g[i] = CP({b[i].x, 0});
        fft(f, 1), fft(g, 1);
        for (int i = 0; i < limit; i++)
            ans[i] = ans[i] + f[i] * g[i], f[i] = g[i] = CP({0, 0});

        for (int i = 0; i < limit; i++)
            f[i] = CP({a[i].x * a[i].x, 0}), g[i] = CP({b[i].x * b[i].x, 0});
        fft(f, 1), fft(g, 1);
        for (int i = 0; i < limit; i++)
            ans[i] = ans[i] - f[i] * g[i] * CP({2, 0}),
            f[i] = g[i] = CP({0, 0});

        for (int i = 0; i < limit; i++)
            f[i] = CP({a[i].x, 0}), g[i] = CP({b[i].x * b[i].x * b[i].x, 0});
        fft(f, 1), fft(g, 1);
        for (int i = 0; i < limit; i++)
            ans[i] = ans[i] + f[i] * g[i], f[i] = g[i] = CP({0, 0});

        fft(ans, -1);
        int t = n + m;
        int cnt = 0;
        for (int i = m; i >= n; i--) {
            if (fabs(ans[i].x)/limit < 1e-1) {
                cnt++;
            }
        }
        cout << cnt << '
';
        for (int i = n; i <= m; i++) {
            if (fabs(ans[i].x) / limit < 1e-1) {
                cout << i + 1 - n << " ";
                cnt++;
            }
        }
    }
}
signed main() {
    ll t = 1;  // cin >> t;
    while (t--) {
        solve();
    }
}