题解 P7114 【[NOIP2020] 字符串匹配】

泥土笨笨 · 2021-02-16 15:35:09 · 题解

我有个梦想，我想写一篇多图的，讲解细的，注释多的，O(nlog26)复杂度的题解。

前置知识

1. 树状数组 这个相信能参加NOIP的同学都会。
2. 扩展KMP算法 模板题：P5410 【模板】扩展 KMP（Z 函数） 这道题我也写了题解，欢迎评论点赞围观。这道模板题是紫色的，其实一点也不难，我觉得难度有点虚标了，相信你看了我的题解很快就可以学会的。

如果你不会扩展KMP算法，其实也不影响你阅读本文，只需知道这个算法提供了一个z函数的计算方式。

不妨设输入的字符串是s，下标从0开始，长度是n。用s[i,j]表示s中从下标i位置到下标j位置的子串，包括i和j。那么z[i]表示s[i,n-1]与s本身的最长公共前缀的长度。

比如z[0]表示s与s的公共子串的长度，那么z[0]=n

考虑k的取值。如果k的值是奇数:

如图所示，k=1时候，C的长度是从i开头的后缀的长度。k=3的时候，C是更短的红线表示的范围。这两种情况下，C当中出现次数为奇数的字符的个数是一样多的，因为如果循环节多出现了两次，相当于循环节里面的每个字符都出现了偶数次，不影响C当中出现次数为奇数次的字符的个数。

所以，当k是奇数的时候，我们只需计算出来，以i为开头的后缀当中出现奇数次的字符的个数就行了。然后在长度为i的子串的前缀s[0,j]当中，找出来满足：

的j的个数，记为t1。而对于每个合法的j，我们发现，只要是奇数的k，都可以是一种合法方案，所以这里要乘法原理一下，把t1和tj的个数相乘。

再来考虑k是偶数的情况。

跟前面情况类似，当k是偶数的时候，后缀C里面的只出现奇数次的字符的个数，和整个串里面只出现奇数次的字符个数是相等的。在长度为i的子串的前缀s[0,j]当中，找出来满足：

的j的个数，记为t2。那么这种情况下的方案数，就是t2和to相乘。

具体实现

首先前面的算法中用到了f(0,n-1)，这个好办，直接预处理算出来就行了。

在从左往右扫字符串s的过程中，假设我们目前枚举到位置i，此时我们计算循环节长度为i+1的情况，此时A最远可以取到i-1位置，把i位置留着给B，保证B不为空。我们可以用一个桶，维护i+1开头的后缀里面每个字母出现的次数，当i向右循环的时候，每次只改一个字符，所以在桶的对应位置减1，然后看看出现奇数次的字符数量如何变化就行了。

不妨设这个桶叫after，一共有26个格，分别表示每个字符出现的次数。起始的时候，先扫一遍s，把整个字符串都统计一遍，这时候可以顺手求出整个串里面只出现奇数次的字符的个数，记到all变量里面。然后当后面循环的时候，循环到i位置，就把after[s[i]-'a']位置减1。设变量suf表示f[i+1,n-1]，如果在after[s[i]-'a']减1之前，suf是奇数，那么减完以后，后缀里面的奇数就会少一个，那么suf减1，否则suf加一。这样每次i移动，suf都可以O(1)维护。

那么循环节里面的每个前缀中出现奇数次的字符个数，可以放到一个树状数组里面，这样这个树状数组一共有26个位置，每个位置p保存出现奇数次的字符有p个的前缀有多少个。i每向右循环1位，就在计算完结果以后，把当前前缀扔到树状数组里面。

其他细节可以参考代码

代码时间

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int MAXN = (1 << 20) + 5;
char s[MAXN];//输入的字符串
int n, z[MAXN];//字符串长度，以及z函数的值
int before[30], after[30];//两个桶，分别统计当前枚举到的位置左侧和右侧每个字符出现的频次
int pre, suf, all;//当前枚举到的位置的前缀、后缀、整个串里面出现奇数次的字符的个数

//树状数组，对于s的某个前缀si，如果它里面出现奇数次的字符有m个，则在树状数组m+1位置+1
int c[30];

inline int lbt(int x) {
    return x & -x;
}

void update(int x) {
    while (x <= 27) {
        c[x]++;
        x += lbt(x);
    }
}

int sum(int x) {
    int r = 0;
    while (x > 0) {
        r += c[x];
        x -= lbt(x);
    }
    return r;
}

//扩展KMP算法，计算z函数的值
//可以参考良心博客 https://www.luogu.com.cn/blog/nitubenben/solution-p5410
void Z() {
    z[0] = n;
    int now = 0;
    while (now + 1 < n && s[now] == s[now + 1]) {
        now++;
    }
    z[1] = now;
    int p0 = 1;
    for (int i = 2; i < n; ++i) {
        if (i + z[i - p0] < p0 + z[p0]) {
            z[i] = z[i - p0];
        } else {
            now = p0 + z[p0] - i;
            now = max(now, 0);
            while (now + i < n && s[now] == s[now + i]) {
                now++;
            }
            z[i] = now;
            p0 = i;
        }
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> s;
        n = strlen(s);
        memset(before, 0, sizeof(before));
        memset(after, 0, sizeof(after));
        memset(c, 0, sizeof(c));
        all = pre = suf = 0;
        Z();
        //如果发现循环节可以到结尾，减1，空至少一个位置给C
        for (int i = 0; i < n; ++i) {
            if (i + z[i] == n) z[i]--;
        }
        //先把字符串过一遍，频次统计到after数组里面
        for (int i = 0; i < n; ++i) {
            after[s[i] - 'a']++;
        }
        //扫一下每个字母，计算整个串中出现奇数次的字符的个数
        for (int i = 0; i < 26; ++i) {
            if (after[i] & 1) {
                all++;
            }
        }
        suf = all;//后缀中的值暂时和整个串一致
        long long ans = 0;
        for (int i = 0; i < n; ++i) {
            //再扫一次字符串，当循环到i位置的时候，循环节长度是i+1
            //s[i]要从右边去掉，维护after数组和suf变量
            if (after[s[i] - 'a'] & 1) {
                //之前是奇数，现在变成偶数了
                suf--;
            } else {
                suf++;
            }
            after[s[i] - 'a']--;
            //s[i]加到左边，维护before和pre变量
            if (before[s[i] - 'a'] & 1) {
                pre--;
            } else {
                pre++;
            }
            before[s[i] - 'a']++;
            if (i != 0 && i != n - 1) {
                //循环节大于1,才能对答案有贡献，因为题中说ABC都不为空
                int t = z[i + 1] / (i + 1) + 1;
                ans += 1LL * (t / 2) * sum(all + 1) + 1LL * (t - t / 2) * sum(suf + 1);
            }
            update(pre + 1);
        }
        cout << ans << endl;
    }
    return 0;
}