P9089「SvR-2」Work

FISHER_ · 2023-02-19 10:34:02 · 题解

基于 AC 自动机的线性解法。

把所有串都反过来，这样一个串有意义当且仅当它可以分解成若干个前缀。

定义一个串的匹配是它的一个后缀与某个 s_i 的前缀相同，这个后缀就是它的一个匹配。

考虑一个串 S 有意义的充分条件是 S 的每一个前缀都有匹配。容易发现这也是必要条件。

由此给出一个验证一个串是否有意义的方法：选择 S 的一个匹配，删掉它，重复这个过程。如果删光了就是有意义的。

现在给你一个字符串 S，问你 S 有几个后缀有意义。沿用刚才的办法，贪心地每次删掉一个最短的匹配，直到删光或者不存在匹配，容易发现删除次数就是所求。

对于每一个串的每一个前缀，都要求出答案，考虑简单 DP：

其中 \text{MinMatching}(i) 是 S 长度为 i 的前缀的最短匹配。

最短匹配可以用 AC 自动机来求。至此我们得到了一个 O(|\Sigma|\sum |s_i|) 的解法。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 500000, maxs = 1000000;
string s[maxn + 5];
int pcnt;
int nxt[maxs + 5][26];
int len[maxs + 5];
int fail[maxs + 5], mf[maxs + 5];
int insert(const string& str) {
    int n = str.size(), p = 0;
    for (int i = 0; i < n; i++) {
        int c = str[i] - 'a';
        if (!nxt[p][c]) nxt[p][c] = ++pcnt;
        len[p = nxt[p][c]] = i + 1;
    }
    return p;
}
void build() {
    queue<int> q;
    for (int i = 0; i < 26; i++)
        if (nxt[0][i]) q.push(nxt[0][i]);
    while (q.size()) {
        int u = q.front();
        q.pop();
        mf[u] = fail[u] ? mf[fail[u]] : len[u];
        for (int i = 0; i < 26; i++) {
            if (nxt[u][i]) {
                fail[nxt[u][i]] = nxt[fail[u]][i];
                q.push(nxt[u][i]);
            } else nxt[u][i] = nxt[fail[u]][i];
        }
    }
}
int f[maxs + 5];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        reverse(s[i].begin(), s[i].end());
        insert(s[i]);
    }
    build();
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        int m = s[i].size(), p = 0;
        fill(f, f + m + 1, 0);
        for (int j = 0; j < m; j++) {
            int c = s[i][j] - 'a';
            p = nxt[p][c];
            if (mf[p]) f[j + 1] = f[j - mf[p] + 1] + 1;
            ans += f[j + 1];
        }
    }
    printf("%lld", ans);
}