[NOIP2020] 字符串匹配（数学解决字符串问题）

sandom · 2022-11-09 11:58:40 · 个人记录

预处理出前缀 F 和后缀 F，分别记作 f 和 g，然后考虑暴力做法： 枚举 C 的长度，在前面找 AB 循环节，对于每个循环节都要计算出合法的 A 的方案。

发现有很多重复步骤，并且计算式形如枚举约数，那就可以考虑筛法。

下文的 cycle 数组为最小循环节的长度，可以通过 kmp 和 nxt 数组求出。

定义 h(t, j)=\sum\limits_{i=1}^{j}[f(i)<=t] 表示 j 前面合法的 A，目的是对于每一个循环节都能O(1)找出A的合法方案数。

定义 t(n)=\sum\limits_{j|n\ and\ cycle_n|j}h(g_{i+1}, j-1)，表示对于一个长度为 n 的字符串，后面为 C 串，前面的合法数量。显然一个循环节可以由最小循环节拼出来，并且长度要整除串长。因为B至少要有一个，所以是j-1。

复杂度为 O(Tn(logn+26))，时间复杂度有些劣，但是很好想，其实就是优化暴力，有一定筛法功底的人都能想出来。

核心代码如下

void init()
{
    memset(cnt, 0, sizeof(cnt)); f[0] = 0;
    rep(i, 1, n) f[i] = f[i - 1] + work(s[i] - 'a');
    memset(cnt, 0, sizeof(cnt)); g[n + 1] = 0;
    dwn(i, n, 1) g[i] = g[i + 1] + work(s[i] - 'a');
    rep(t, 0, 26) rep(i, 1, n)
        h[t][i] = h[t][i - 1] + (f[i] <= t);
    memset(t, 0, sizeof(t));
    rep(j, 1, n) for (int i = j; i <= n; i += j)
        if (j % cyc[i] == 0) t[i] += h[g[i + 1]][j - 1];
}