匹配统计解题过程

lvvd · 2023-10-09 15:29:21 · 个人记录

link

第一眼是哈希加二分，可以通过。

理论存在，实践开始。

#include <bits/stdc++.h>
namespace VividCycle {
    #include <bits/stdc++.h>
    // #define getchar gc
    #define putchar pc
    #define fu(i, l, r) for(int i = l; i <= r; ++i)
    #define fd(i, l, r) for(int i = l; i >= r; --i)
    #define fo(i, v) for(const auto& i : v)
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    static char buffer[1 << 20 | 1]; static int outp = -1;
    void flush() {fwrite(buffer, 1, outp + 1, stdout), outp = -1;}
    void pc(const char& ch) {if(outp == (1 << 20)) flush(); buffer[++outp] = ch;}
    char gc() {static char ibuf[1 << 20], *p1 = ibuf, *p2 = ibuf; return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1000010, stdin), p1 == p2) ? -1 : *p1++;}
    template<typename T> void read(T& x) {x = 0; int f = 1; char ch = getchar(); while(ch < '0' || ch > '9') f *= ((ch == '-') ? -1 : 1), ch = getchar(); while(ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); x *= f;}
    template<typename T, typename ...Args> void read(T& x, Args& ...args) {read(x), read(args...);}
    void write(const char& ch) {putchar(ch);} void write(const char s[]) {int len = strlen(s) - 1; fu(i, 0, len) putchar(s[i]);} void write(char s[]) {int len = strlen(s) - 1; fu(i, 0, len) putchar(s[i]);}
    template<typename T> void write(T x) {static char obuf[1 << 8]; static int p; p = 0; if(x < 0) x *= (putchar('-'), -1); if(!x) {putchar('0'); return;} while(x) obuf[++p] = x % 10 ^ 48, x /= 10; while(p) putchar(obuf[p--]);}
    template<typename T, typename ...Args> void write(T x, Args ...args) {write(x), write(args...);}
}
using namespace VividCycle;
const int mul = 299987, mod = 998244353;
ll n, m, q, x, l, r, mid, mx, hsa[200001], hsb[200001], power[200001], ans[200001];
char a[200005], b[200005];
int main() {
    read(n, m, q);
    scanf("%s %s", a + 1, b + 1);
    power[0] = 1;
    fu(i, 1, n) {
        power[i] = power[i - 1] * mul % mod;
        hsa[i] = (hsa[i - 1] * mul + a[i]) % mod;
        // cerr << hsa[i] << " ";
    }
    // cerr << endl;
    fu(i, 1, m) {
        hsb[i] = (hsb[i - 1] * mul + b[i]) % mod;
        // cerr << hsb[i] << " ";
    }
    // cerr << endl;
    // cerr << "!" << (hsa[3] - hsa[1] * power[2] % mod + mod) % mod << endl;
    fu(i, 1, n) {
        l = i - 1, r = min(i + m - 1, n), mx = 0;
        while(l <= r) mid = (l + r) >> 1, (hsb[mid - i + 1] == (hsa[mid] - hsa[i - 1] * power[mid - i + 1] % mod + mod) % mod) ? (mx = mid - i + 1, l = mid + 1) : (r = mid - 1);
        ++ans[mx];
        // cerr << i << "-" << mx << endl;
    }
    while(q--) {
        read(x);
        write(ans[x], '\n');
    }
    flush();
    return 0;
}

但是应该有 KMP 做法。

回想一下 KMP 的匹配过程，其实容易发现每个位置的匹配大小就是它的最长匹配。

倒着处理就好。

理论存在，实践不了，开摆。

事实证明倒着处理不行，wssb

匹配统计 解题过程

匹配统计解题过程