DDOSvoid's Blog

Luogu P7114 [NOIP2020] 字符串匹配

发表于 分类于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/P7114

简要题意：给定一个字符串 $S$，求 $S$ 的所有合法的 拆分方案，$S$ 的一个拆分我们定义为 $S=(AB)^kC$，其中 $A,B,C$ 均为非空字符串，且 $A$ 中出现奇数次的字符数量不超过 $C$ 中出现奇数次的字符数量，$k$ 为正整数，两个方案不同当且仅当 $A,B,C$ 至少一个字符不同

$T\le 5,S\le 2^{20}$​

Solution

我们考虑枚举 $AB$ 的长度然后枚举重复出现次数，用 $hash$ 来判断，用树状数组维护 $A$ 的贡献，这样的时间复杂度是 $O(Tn\log n\log 26)$​，不足以通过此题

我们发现对于固定的 $AB$，出现次数只有奇数和偶数两种情况，那么现在的瓶颈在于如何快速得到出现次数，我们考虑借助扩展 $KMP$ 的 $z$ 数组，容易得到 $per(S,i)$ 的前缀重复出现次数为 $\lfloor \frac{z[i+1]}{i}\rfloor+1$

时间复杂度 $O(Tn\log 26)$，好像有严格 $O(Tn)$ 的做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstring>
#define maxn 1100010
#define lowbit(i) ((i) & (-i))
#define ll long long
using namespace std;

int Bit[30];

void add(int i, int v) { ++i; while (i <= 27) Bit[i] += v, i += lowbit(i); }
int get_sum(int i) {
    int s = 0; ++i;
    while (i) s += Bit[i], i -= lowbit(i);
    return s;
}

int z[maxn];
void init_Z(char *s) {
    int n = strlen(s + 1); z[1] = n;
    for (int i = 2, l = 0, r = 0; i <= n; ++i) {
        z[i] = i <= r ? min(z[i - l + 1], r - i + 1) : 0;
        while (i + z[i] <= n && s[i + z[i]] == s[z[i] + 1]) ++z[i];
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
}
    
int n;
char s[maxn];

int suf[maxn], cnt[26];

void work() {
    cin >> s + 1; n = strlen(s + 1); init_Z(s);
    ll ans = 0; int sum = 0; 
    for (int i = 0; i < 26; ++i) cnt[i] = 0; 
    for (int i = n; i; --i) {
        if (cnt[s[i] - 'a']) --sum;
        else ++sum; cnt[s[i] - 'a'] ^= 1; suf[i] = sum;
    } fill(Bit, Bit + 30, 0);
    for (int i = 0; i < 26; ++i) cnt[i] = 0; 
    cnt[s[1] - 'a'] = sum = 1; add(sum, 1); 
    for (int i = 2; i < n; ++i) {
        ll t = z[i + 1] / i + 1; if (i * t == n) --t;
        ans += (t + 1) / 2 * get_sum(suf[i + 1]);
        if (2 * i < n) ans += t / 2 * get_sum(suf[2 * i + 1]); 
        if (cnt[s[i] - 'a']) --sum;
        else ++sum; cnt[s[i] - 'a'] ^= 1;
        add(sum, 1); 
    } cout << ans << "\n";
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
    return 0; 
}