[NOIP2020] 字符串匹配

· · 题解

[NOIP2020] 字符串匹配

首先，可以把 AB 看成一个整体。

那么就可以枚举出所有长度下的 AB，知道 AB 后就可以求出 C，因为枚举的是AB，所以长度小于 |AB| 的 A 都是可行的。

那么查询有多少个前缀串 T，满足 |T|<|AB| 且 F(T)\le F(C) 即可。

枚举这个 AB 是一个调和级数，O(n\log n) 的（匹配两个串就用哈希）。

然后求有多少个 F(T)\le F(C) 用树状数组维护就行了。

（F(T) 和 F(C) 的值都可以预处理出来）。

树状数组维护的是字符集大小，所以最后复杂度就是 O(n \log n\log 26)。

#include <bits/stdc++.h>
#define ull unsigned long long

void Freopen() {
    freopen("", "r", stdin);
    freopen("", "w", stdout);
}

using namespace std;
const int N = 1.1e6 + 10, M = 2e5 + 10, inf = 1e9, mod = 998244353;

int pF[N], sF[N];
int cnt[26], vis[26];
char s[N];
int n;

int tr[N];

void add( int x) {
    for (; x <= 27; x += (x & -x)) tr[x] += 1;
}

int ask( int x, int res = 0) {
    for (; x; x -= (x & -x)) res += tr[x];

    return res;
}

ull hsh[N], pw[N], base = 133337;

ull query( int l, int r) {
    return hsh[r] - hsh[l - 1] * pw[r - l + 1];
}

void solve() {
    cin >> (s + 1);

    n = strlen(s + 1);

    for ( int i = 1; i <= n; i ++) hsh[i] = hsh[i - 1] * base + s[i];

    for ( int i = 0; i <= n + 1; i ++) tr[i] = pF[i] = sF[i] = 0;

    memset(cnt, 0, sizeof cnt);

    for ( int i = 1; i <= n; i ++) {
        cnt[s[i] - 'a'] ++;

        if (cnt[s[i] - 'a'] & 1) pF[i] = pF[i - 1] + 1;
        else pF[i] = pF[i - 1] - 1;
    }

    memset(cnt, 0, sizeof cnt);

    for ( int i = n; i; i --) {
        cnt[s[i] - 'a'] ++;

        if (cnt[s[i] - 'a'] & 1) sF[i] = sF[i + 1] + 1;
        else sF[i] = sF[i + 1] - 1;
    }

    ull ans = 0;

    for ( int len = 1; len <= n; len ++) {
        int l = 1, r = 1 + len - 1;

        ull hs = query(l, r);

        while (r <= n && query(l, r) == hs) {
            if (r < n) ans += ask(sF[r + 1] + 1);

            l += len, r += len;
        }

        add(pF[len] + 1);
    }

    cout << ans << '\n';
}

signed main() {
    ios :: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int t;

    pw[0] = 1;
    for ( int i = 1; i < N; i ++) pw[i] = pw[i - 1] * base;

    for (cin >> t; t; t --) solve();
}