题解：AT_abc268_h [ABC268Ex] Taboo

· · 题解

提供一个不用脑子的思路。

如果已经算出每个串的每个出现位置，相当于现在有若干个区间，你要在 1\sim n 上选若干个点，使得每个区间至少覆盖一个点，并最小化选的点数。

这是个典型的贪心问题。如果取了一个点，则这个点右移到 所有覆盖了它的区间的交集 的右端点不影响答案，而 这个交集的右端点 一定是 某个区间的右端点。所以我们只需要考虑在某个区间的右端点上选点。

所以我们把所有区间按照右端点从小到大排序，枚举当前右端点 r，假设 [1,r-1] 的子区间均满足题目条件，我们想让 [1,r] 的子区间均满足条件，只需要考虑所有右端点为 r 的区间。

维护最后一个选了的点 R，则点 r 要被选当且仅当存在一个区间满足右端点为 r，左端点 >R。此时选上点 r 并更新 R=r 即可。

于是我们只需要对于每个 r 维护出最大的 l，使得 [l,r] 与某个 T_i 匹配。AC 自动机即可，复杂度线性。

// Problem: [ABC268Ex] Taboo
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_abc268_h
// Memory Limit: 1 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define R(i, x, y) for (int i = (x); i >= (y); i--)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
bool Mbe;

const int N = 5e5 + 5;
const int M = 26;

int n, m, ans;
string s, t;

struct ACAM {

    struct T { 
        int fl, l, ch[M]; 
    } t[N];

    int tot;

    ACAM () { tot = 1; }

    void i(string s) {
        int u = 1, len = s.length();
        F (i, 0, len - 1) {
            int v = s[i] - 'a';
            if (!t[u].ch[v]) {
                t[u].ch[v] = ++tot;
                t[tot].l = n + 1;
            }
            u = t[u].ch[v];
        }
        t[u].l = min(t[u].l, len);
    }

    void g() {
        queue<int> q;
        q.push(1);
        F (i, 0, M - 1) {
            t[0].ch[i] = 1;
        }
        t[1].l = n + 1;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            F (i, 0, M - 1) {
                int &v = t[u].ch[i], f = t[u].fl;
                if (!v) {
                    v = t[f].ch[i];
                } else {
                    t[v].fl = t[f].ch[i];
                    t[v].l = min(t[v].l, t[t[v].fl].l);
                    q.push(v);
                }
            }
        }
    }
} A;

void solve() {
    cin >> s >> m;
    n = s.length();
    F (i, 1, m) {
        cin >> t;
        A.i(t);
    }
    A.g();
    int u = 1, R = -1;
    F (r, 0, n - 1) {
        u = A.t[u].ch[s[r] - 'a'];
        if (R <= r - A.t[u].l) {
            ans++;
            R = r;
        }
    }
    cout << ans << '\n';
}

bool Med;
int main() {
    // FIO("");
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
    int T = 1;
    // cin >> T;
    while (T--) solve();
    cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
    return 0;
}