给定一个小写串 $s$ 以及 $n$ 个小写串 $t_{1\sim n}$，在 $s$ 中修改最少的字符为 *，是的所有 $t$ 都不会在 $s$ 中出现。

这里我是用 AC 自动机做的，找出所有 $t$ 在 $s$ 中的位置，问题转化为：给定一些区间，放置尽量少的点，使得每个区间中都有点。但是这个区间数量是 $O(n^2)$ 级别。求优化

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 5e5 + 10;

int ch[MAXN][26], fail[MAXN], tot;

int elen[MAXN];

inline 
void insert(char *s) {
	int len = strlen(s), k = 0;
	for (int i = 0; i < len; i++) {
		if (!ch[k][s[i] - 'a']) ch[k][s[i] - 'a'] = ++tot;
		k = ch[k][s[i] - 'a'];
	}
	elen[k] = len;
}

inline 
void build() {
	queue<int> q;
	for (int i = 0; i < 26; i++) {
		if (ch[0][i]) q.push(ch[0][i]);
	}
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int i = 0; i < 26; i++) {
			if (ch[u][i]) fail[ch[u][i]] = ch[fail[u]][i], q.push(ch[u][i]);
			else ch[u][i] = ch[fail[u]][i];
		}
	}
}

int maxr, ans;

inline 
void find(char *s) {
	int len = strlen(s), k = 0;
	for (int i = 0; i < len; i++) {
		k = ch[k][s[i] - 'a'];
		for (int p = k; p; p = fail[p]) {
			if (elen[p] && i - elen[p] + 2 > maxr) ans++, maxr = i + 1;
		}
	}
}

int n, m;

char s[MAXN], t[MAXN];

int main() {
	scanf("%s%d", s, &m), n = strlen(s);
	for (int i = 1; i <= m; i++) scanf("%s", t), insert(t);
	build(), find(s);
	printf("%d", ans);
}