luoguP7114 [NOIP2020] 字符串匹配

暴力骗分？其实是 Z 函数

字符串匹配

思路

正解是广义 KMP （ Z 函数）

但如果你和我一样不会的话（upd ：没想到吧，我会了！），也可以用 KMP 骗到 $84pts$

考虑枚举每一个 $c$ ，设 $s$ 去掉 $c$ 后为 $t$ ，求出 $t$ 的最小循环节，发现 $|AB|$ 必须是它的约数，直接枚举约数，计算贡献即可

关于求最小循环节，有一个结论：对于长度为 $len$ 的串，若 $len - ne[len] \mid len$ ，则最小循环节就是 $len - ne[len]$ ，否则就是 $len$

打个表发现范围内约数最多的数有 $240$ 个约数，总时间为 $O(240Tn)$ ，只有 $1s$ 就只有 $84pts$ 了

代码

一个细节是 vector 存约数因为内存不连续慢点一比（预处理就用了 $1.2s$ ，所以我手动分配内存）

#include <bits/stdc++.h>
#define IL inline
namespace FIO
{
	const int L = (1 << 20) + 5;
	int l = 0;
	char buf[L], out[L], *S, *E;
	#define gh() (S == E ? E = (S = buf) + fread(buf, 1, L, stdin), (S == E ? EOF : *S++) : *S++)
	IL void flus(){ fwrite(out, 1, l, stdout), l = 0; }
	IL void chk(){ if (l >= L - 5) flus(); }
	template<class T>
	IL void read(T &x)
	{
		char ch = gh(), t = 0;
		for (; ch < '0' || ch > '9'; ch = gh()) t |= ch == '-';
		for (x = 0; ch >= '0' && ch <= '9'; ch = gh()) x = x * 10 + (ch ^ 48);
		if (t) x = -x;	
	}
    IL void readc(char *x)
    {
        char ch = gh();
		for (; ch < 'a' || ch > 'z'; ch = gh());
		for (; ch >= 'a' && ch <= 'z'; ch = gh()) *x++ = ch;
        *x = '\0';
    }
	IL void putc(char x){ out[l++] = x, chk(); }
	template<class T>
	IL void write(T x)
	{
		if (x < 0) putc('-'), x = -x;
		if (x > 9) write(x / 10);
		out[l++] = x % 10 + 48, chk();
	}
	#undef gh
} 
using FIO::flus;
using FIO::read;
using FIO::putc;
using FIO::write;
using FIO::readc;
using LL = long long;
const int N = (1 << 20) + 1, A = 30, FN = 14698342 + 100;
int n, ne[N + 5], num[N + 5][A], ct, cnt[A], b[N + 5], fac[FN];
LL ans = 0;
char s[N + 5];
IL LL ask(int l, int r, int up)
{
    return num[r][up] - (l ? num[l - 1][up] : 0);
}
int main()
{
    for (int i = 1; i < N; ++i)
        for (int j = 1; LL(i) * j < N; ++j) ++b[i * j];
    for (int i = 2; i < N; ++i) b[i] += b[i - 1];
    for (int i = N - 1; i; --i) b[i] = b[i - 1];
    for (int i = 1; i < N; ++i)
        for (int j = 1; LL(i) * j < N; ++j) fac[++b[i * j]] = i;
    int T;
    for (read(T); T--; )
    {
        readc(s + 1), n = strlen(s + 1);
        ne[1] = ans = 0;
        for (int i = 2, j = 0; i <= n; ++i)
        {
            while (j && s[i] != s[j + 1]) j = ne[j];
            if (s[i] == s[j + 1]) ++j;
            ne[i] = j;
        }
        memset(num, 0, sizeof num);
        memset(cnt, 0, sizeof cnt), ct = 0;
        for (int i = 1; i <= n; ++i)
        {
            ((++cnt[s[i] - 'a']) & 1) ? ++ct :--ct;
            num[i][ct] = 1;
        }
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j < 26; ++j) num[i][j] += num[i][j - 1];
        for (int j = 0; j < 26; ++j)
            for (int i = 2; i <= n; ++i) num[i][j] += num[i - 1][j];
        memset(cnt, 0, sizeof cnt), ct = 0;
        for (int i = n, len = i - 1, p, np, now, last, si; i >= 2; --i, --len)
        {
            ((++cnt[s[i] - 'a']) & 1) ? ++ct : --ct;
            if (len % (p = len - ne[len])) p = len;
            np = len / p, last = 0, si = b[np] - b[np - 1];
            for (int j = b[np - 1] + 1, t = b[np]; j <= t; ++j)
            {
                now = fac[j];
                ans += ask(last * p, now * p - 1, ct) * si;
                --si, last = now;
            }
        }
        write(ans), putc('\n');
    }
    return flus(), 0;
}

upd：可过的思路

被迫学了 Z 函数，现在回来填坑

考虑枚举 $AB$ ，设当前枚举到 $AB = s[1 \sim i]$ ，且 $AB$ 循环了 $k$ 次，那么必有 $ik \le i + Z[i + 1]$ （这也是循环串的一个结论，类似 kmp 画个图其实很显然），于是有 $k \le K = \lfloor \frac{i + Z[i + 1]}{i} \rfloor$ ，那明显，当前 $AB$ 会被算 $K$ 次

但问题在于必须保证 $A$ 中奇数字符不多于 $C$ ，不难发现 $C$ 的奇数字符个数其实只有两种（因为它每次加一个循环节），如果我们有最短的 $C$ 的每个字符的出现次数和当前 $AB$ 中每个每个字符的出现次数，提前预处理每一个最短的 $C$ ，就可以在 $O(26)$ 的时间里计算出这两个值，且它们在 $K$ 次中各一半

有了这两个值，考虑同时维护一个树状数组，可以 $O(\log 26)$ 查询“所有满足 $j < i$ ， $A = s[1 \sim j]$ 的 $A$ 中奇数字符个数 $\le x$ 的个数”

发现时间瓶颈在计算 $C$ 的奇数字符个数，其实对于每个字符我们只关心它的奇偶性不关心具体数量，所以用一个 bitset 优化，时间降至 $O(\frac{26}{w}) < O(1)$ （瓶颈就直接变成树状数组了），总时间变成 $O(Tn(\log n + \frac{26}{w}))$ 可过

ps：好像有巨佬用桶 + 每次加减变化量可以做到 $O(n)$ 但实测没快多少，反正目前（2022/4/27）loj 上我的代码是最快的

代码

#include <bits/stdc++.h>
using LL = long long;
const int N = (1 << 20) + 100;
int n, Z[N];
char s[N];
LL ans;
std::bitset<26> ab, a, c[N];
namespace BIT
{
    #define lb(x) ((x) & (-(x)))
    int ct[30];
    void add(int x, int d){ for (++x; x <= 27; x += lb(x)) ct[x] += d; }
    int ask(int x)
    {
        int res = 0;
        for (++x; x; x ^= lb(x)) res += ct[x];
        return res;
    }
    void clear(){ memset(ct, 0, sizeof ct); }
    #undef lb
}
void get_z(char x[], int len)
{
    memset(Z, 0, sizeof Z);
    Z[1] = len;
    for (int i = 2, l = 0, r = 0; i <= len; ++i)
    {
        if (i <= r) Z[i] = std::min(Z[i - l + 1], r - i + 1);
        while (i + Z[i] <= len && x[i + Z[i]] == x[1 + Z[i]]) ++Z[i];
        if (r < Z[i] + i - 1) r = Z[i] + i - 1, l = i;
    }
}
void get_c()
{
    c[n].reset(), c[n].flip(s[n] - 'a');
    for (int i = n - 1; i >= 3; --i) c[i] = c[i + 1], c[i].flip(s[i] - 'a');
}
int main()
{
    int T;
    for (scanf("%d", &T); T--; printf("%lld\n", ans))
    {
        scanf("%s", s + 1), n = strlen(s + 1);
        get_z(s, n), ab.reset(), a.reset(), BIT::clear(), get_c(), ans = 0;
        ab.set(s[1] - 'a');
        for (int i = 2, k, t1, t2; i < n; ++i)
        {
            k = (Z[i + 1]) ? (i + Z[i + 1]) / i : 1;
            if (i * k >= n) --k;
            a.flip(s[i - 1] - 'a');
            BIT::add(a.count(), 1);
            ab.flip(s[i] - 'a');
            auto cc = c[i * k + 1];
            t1 = BIT::ask(cc.count());
            cc = cc ^ ab;
            t2 = BIT::ask(cc.count());
            ans += LL(t1 + t2) * (k >> 1);
            if (k & 1) ans += t1;
        }
    }
    return 0;
}