Siyuan

「Luogu 4173」残缺的字符串
「Luogu 4173」残缺的字符串
扫描右侧二维码阅读全文
03
2019/08

「Luogu 4173」残缺的字符串

题目链接:Luogu 4173

很久很久以前,在你刚刚学习字符串匹配的时候,有两个仅包含小写字母的字符串 $A$ 和 $B$,其中 $A$ 串长度为 $m$,$B$ 串长度为 $n$。可当你现在再次碰到这两个串时,这两个串已经老化了,每个串都有不同程度的残缺。

你想对这两个串重新进行匹配,其中 $A$ 为模板串,那么现在问题来了,请回答,对于 $B$ 的每一个位置 $i$,从这个位置开始连续 $m$ 个字符形成的子串是否可能与 $A$ 串完全匹配?

数据范围:$1 \le m \le n \le 3 \times 10 ^ {5}$。


Solution

字符串匹配问题可以使用 $\text{FFT}$ 解决。

首先我们定义通配符为 * 为 $0$,其余字母分别按顺序标号为 $1$ 到 $26$。

我们对于两个长度相同的字符串 $A, B$ 构造匹配函数:

$$ \begin{align*} F(A, B) & = \sum_{i = 0} ^ {n - 1} (A_{i} - B_{i}) ^ {2} A_{i} B_{i} \\ & = \sum_{i = 0} ^ {n - 1} \left ({A_{i}} ^ {3} B_{i} - 2 {A_{i}} ^ {2} {B_{i}} ^ {2} + A_{i} {B_{i}} ^ {3} \right ) \end{align*} $$

两个字符串完全匹配的充要条件是 $F(A, B) = 0$。

这明显是一个卷积形式,把 $A$ 翻转后 $\text{FFT}$ 求出所有值为 $0$ 的下标。

吐槽:竟然 $\text{NTT}$ 也能通过本题,出题人怎么连常用模数都没卡呀……

时间复杂度:$\mathcal O(n \log n)$,自带超大常数(需要 $7 \sim 9$ 次 $\text{FFT}$)。


Code

/* 此处省略多项式模板 */

const int N = 3e5 + 5;

int n, m;
char s[N], t[N];

Vec solve(Vec A, Vec B) {
    Vec P(n);
    std::reverse(A.begin(), A.end());
    int n1 = A.size(), n2 = B.size(), n = extend(n1 + n2 - 1);

    Vec F = A, G = B;
    for (auto &x : F) x = 1LL * x * x % MOD * x % MOD;
    F.resize(n), G.resize(n), DFT(F), DFT(G);
    for (int i = 0; i < n; i++) F[i] = 1LL * F[i] * G[i] % MOD;
    P = P + F;
    
    F = A, G = B;
    for (auto &x : F) x = 1LL * x * x % MOD;
    for (auto &x : G) x = 1LL * x * x % MOD;
    F.resize(n), G.resize(n), DFT(F), DFT(G);
    for (int i = 0; i < n; i++) F[i] = 1LL * F[i] * G[i] % MOD;
    P = P - 2 * F;
    
    F = A, G = B;
    for (auto &x : G) x = 1LL * x * x % MOD * x % MOD;
    F.resize(n), G.resize(n), DFT(F), DFT(G);
    for (int i = 0; i < n; i++) F[i] = 1LL * F[i] * G[i] % MOD;
    P = P + F;

    IDFT(P), P.resize(n1 + n2 - 1);

    return P;
}
int main() {
    scanf("%d%d%s%s", &m, &n, s, t);
    Vec A(m), B(n);
    for (int i = 0; i < m; i++) A[i] = (s[i] == '*' ? 0 : s[i] - 'a' + 1);
    for (int i = 0; i < n; i++) B[i] = (t[i] == '*' ? 0 : t[i] - 'a' + 1);
    Vec F = solve(A, B), ans;
    for (int i = m - 1; i < n; i++) {
        if (F[i] == 0) ans.emplace_back(i - m + 2);
    }
    printf("%d\n", (int)ans.size());
    print(ans);
    return 0;
}

2 条评论

  1. KH
  2. sssaj

发表评论