洛谷P7114 [NOIP2020] 字符串匹配题解

题目链接：P7114 [NOIP2020] 字符串匹配

题意：

cxy 和妹纸一起学习完了字符串匹配的相关内容，现在她正在做一道习题。

对于一个字符串 \(S\)，题目要求她找到 \(S\) 的所有具有下列形式的拆分方案数：

\(S = ABC\)，\(S = ABABC\)，\(S = ABAB \ldots ABC\)，其中 \(A,B,C\) 均是非空字符串，且 \(A\) 中出现奇数次的字符数量不超过 \(C\) 中出现奇数次的字符数量。

更具体地，我们可以定义 \(AB\) 表示两个字符串 \(A,B\) 相连接，例如 \(A = \texttt{aab}\)，\(B = \texttt{ab}\)，则 \(AB = \texttt{aabab}\)。

并递归地定义 \(A^1=A\)，\(A^n = A^{n - 1} A\)（\(n \ge 2\) 且为正整数）。例如 \(A = \texttt{abb}\)，则 \(A^3=\texttt{abbabbabb}\)。

则 cxy 的习题是求 \(S = {(AB)}^iC\) 的方案数，其中 \(F(A) \le F(C)\)，\(F(S)\) 表示字符串 \(S\) 中出现奇数次的字符的数量。两种方案不同当且仅当拆分出的 \(A,B,C\) 中有至少一个字符串不同。

可爱的 cxy 并不会做这道题，只好向你求助，请你帮帮她。

输入格式：

本题有多组数据，输入文件第一行一个正整数 \(T\) 表示数据组数。

每组数据仅一行一个字符串 \(S\)，意义见题目描述。\(S\) 仅由英文小写字母构成。

输出格式：

对于每组数据输出一行一个整数表示答案。

数据范围：

对于所有测试点，保证 \(1 \le T \le 5,~1 \le |S| \le 2^{20}\)。

这道题考察的是对 Z 函数的理解，也就是扩展KMP。

考虑枚举循环节 \(AB\) 的长度 \(i\) ，则有 \(2 \le i \le n - 1\) 。

同时不难发现 \((AB)^k\) 中 \(k\) 的方案数为 \(\displaystyle \left\lfloor\frac{z_i}{i-1}\right\rfloor+1\) 。

举个例子，\(i=4,~z_4=7\)，参考下图可知 \(k\) 有 \(\lfloor 7 / 3\rfloor+1=3\) 种取值：

接着考虑出现次数为奇数的问题。不妨记 \(f(l,r)\) 为 \(s[l..r]\) 中出现奇数次的字符的个数。

根据刚刚的结论，记 \(t\) 为 \(k\) 的方案数，其中 \(k\) 为奇数的方案有 \(t - \left\lfloor t/2 \right\rfloor\) 种。

而 \(k\) 的奇偶性对答案的计算有一定影响，因此我们分别来考虑这两种情况。

首先是 \(k\) 为奇数的情况：

图中的红线部分即为 \(C\) 。~~稍加思索~~可以发现上图两段红线的 \(f\) 是相等的，则这部分的贡献为 \[ \left(t - \left\lfloor t/2 \right\rfloor\right) \times \sum_{j\le i} \left[f(1,j) \le f(i+1,n)\right] \] 然后是 \(k\) 为偶数的情况：

此时 \(C\) 中出现奇数次的字符的个数与整个串中出现奇数次的字符个数是相等的，则这部分的贡献为 \[ \left\lfloor t/2 \right\rfloor \times \sum_{j \le i}[f(1,j) \le f(1,n)] \] 实现的时候，我们枚举的循环节长度其实是 \(i+1\) ，这样方便一些。

时间复杂度 \(\mathcal{O}(n \log 26)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)((1 << 20) + 15))

char s[N];
int n,pre,suf,all,z[N],Pre[30],Suf[30],tree[30];
void clear()
{
    pre = suf = all = 0;
    memset(Pre, 0, sizeof(Pre)); memset(Suf, 0, sizeof(Suf));
    memset(tree, 0, sizeof(tree)); memset(z, 0, (n + 5) * sizeof(int));
}
int lowbit(int x) { return x & (-x); }
void add(int x) { for(int i = x; i <= 27; i += lowbit(i)) ++tree[i]; }
int sum(int x) { int c(0); for(int i = x; i; i -= lowbit(i)) c += tree[i]; return c; }
void init()
{
    z[1] = n;
    for(int i = 2, l = 0, r = 0; i <= n; i++)
    {
        if(i <= r) z[i] = min(r - i + 1, z[i - l + 1]);
        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; }
    }
}
void solve()
{
    clear(); cin >> (s + 1); n = strlen(s + 1); init();
    // for(int i = 1; i <= n; i++) cout << z[i] << " \n"[i == n];
    for(int i = 1; i <= n; i++) if(i + z[i] - 1 == n) --z[i];
    for(int i = 1; i <= n; i++) ++Suf[s[i] - 'a'];
    for(int i = 0; i < 26; i++) if(Suf[i] & 1) ++all;
    suf = all; int res = 0;
    for(int i = 1; i <= n; i++)
    {
        { (Suf[s[i] - 'a'] & 1) ? (--suf) : (++suf); } --Suf[s[i] - 'a'];
        { (Pre[s[i] - 'a'] & 1) ? (--pre) : (++pre); } ++Pre[s[i] - 'a'];
        if(i != n)
        {
            int t = z[i + 1] / i + 1;
            res += (t - t / 2) * sum(suf + 1) + (t / 2) * sum(all + 1);
        }
        add(pre + 1);
    }
    cout << res << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; cin >> Q; while(Q--) solve();
    return 0;
}