题意:
给出\(n\)个字符串,这些字符串为致病因子,给出一个字符串,求将这些字符串处理成没有致病因子,最少需要改变多少个字符数量
请问,其中有多少个单词在文章中出现了。
思路:
利用AC自动机来实现多字符串匹配,设f[i][j]
为,前i
个字符,当前匹配到j
。
注意标记哪些点不可取,如果当前的前缀不可取,当前点一定也不可取,因为会包含致病因子。
实现:
#include <stdio.h> #include <algorithm> #include <cstring> using namespace std; const int N = 10010, S = 55, M = 100010; int n, tr[N * S][27], cnt[N * S], idx; char str[M]; int q[N * S], ne[N * S]; void insert() { int p = 0; for (int i = 1; str[i]; i++) { int t = str[i] - 'a' + 1; if (!tr[p][t]) tr[p][t] = idx++; p = tr[p][t]; } cnt[p]++; } void build() { int hh = 1, tt = 0; for (int i = 1; i <= 26; i++) if (tr[0][i]) q[++tt] = tr[0][i]; while (hh <= tt) { int t = q[hh++]; for (int i = 1; i <= 26; i++) { int p = tr[t][i]; if (!p) tr[t][i] = tr[ne[t]][i]; else { ne[p] = tr[ne[t]][i]; q[++tt] = p; } } } } int main() { int _; scanf("%d", &_); while (_--) { memset(tr, 0, sizeof tr); memset(cnt, 0, sizeof cnt); memset(ne, 0, sizeof ne); idx = 1; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%s", str + 1); insert(); } build(); scanf("%s", str + 1); int res = 0; for (int i = 1, j = 0; str[i]; i++) { int t = str[i] - 'a' + 1; j = tr[j][t]; int p = j; while (p) { res += cnt[p]; cnt[p] = 0; p = ne[p]; } } printf("%d\n", res); } return 0; }