问题描述
蒜厂工作手册，你听说过么？蒜头君把蒜厂工作手册全部摘抄了下来并把它变成了一个长度不超过 10^5的字符串 S，蒜头君还有一个包含 n 个单词的列表，列表里的 n 个单词记为 t1⋯tN。他希望从 S 中删除这些单词。 蒜头君每次在 S 中找到第一个出现的列表中的单词，然后从 S 中删除这个单词。他重复这个操作直到 S 中没有列表里的单词为止。需要注意的是删除一个单词后，后面的紧跟着的字符和前面的字符连接起来可能再次出现列表中出现的单词。并且蒜头君注意到列表中的单词不会出现一个单词是另一个单词子串的情况。 请你帮助蒜头君输出删除后的 S。 输入格式 第一行输入一个字符串 S(1≤∣S∣≤105)。 第二行输入一个整数 N(1≤N≤2000)。 接下来的 N 行，每行输入一个字符串，第 i 行的字符串是 ti。 N个字符串的长度和小于10^5。注意：输入的字符串仅包含小写字母。 输出格式 答案输出一行，输出操作后的 S。 样例输入 oorjskorzorzzooorzrzrzr 2 orz jsk 样例输出 or
AC代码
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int MAX_N =
100001;
const int MAX_C =
26;
int a =
0;
struct AC_Automaton {
int ch[MAX_N][MAX_C], fail[MAX_N], cnt[MAX_N], len[MAX_N], p1[MAX_N], top;
int last[MAX_N];
int tot;
void init()
{
memset(ch, -
1,
sizeof(ch));
memset(fail,
0,
sizeof(fail));
tot =
0;
top =
0;
memset(cnt,
0,
sizeof(cnt));
memset(len,
0,
sizeof(len));
}
void insert(
char* str)
{
int p =
0, i, t;
for (i =
0; str[i]; ++i) {
if (ch[p][str[i] -
'a'] == -
1) {
ch[p][str[i] -
'a'] = ++tot;
}
p = ch[p][str[i] -
'a'];
if (i ==
0)
t = p;
}
cnt[p]++;
len[p] = i;
}
void build()
{
int l =
0, r =
0, Q[MAX_N];
for (
int i =
0; i < MAX_C; i++) {
if (ch[
0][i] == -
1) {
ch[
0][i] =
0;
}
else {
Q[r++] = ch[
0][i];
}
}
while (l < r) {
int p = Q[l++];
for (
int i =
0; i < MAX_C; i++) {
if (ch[p][i] == -
1) {
ch[p][i] = ch[fail[p]][i];
}
else {
int v=fail[p];
int u = ch[p][i];
while(v && ch[v][i] == -
1) v=fail[v];
fail[u] = ch[v][i];
Q[r++] = u;
last[u] = cnt[u]? u : last[fail[u]];
}
}
}
}
int count(
char* str)
{
int ret =
0, p =
0;
for (
int i =
0; str[i]; ++i) {
str[a++] = str[i];
p = ch[p][str[i] -
'a'];
p1[top++] = p;
int tmp = last[p];
if (cnt[tmp] >
0) {
a = a - len[tmp];
top = top - len[tmp];
p = p1[top -
1];
}
}
return ret;
}
} Automaton;
int main(
void)
{
char t[MAX_N], s[MAX_N];
int n;
Automaton.init();
scanf(
"%s", s);
cin >> n;
while (n--) {
scanf(
"%s", t);
Automaton.insert(t);
}
Automaton.build();
Automaton.count(s);
s[a] =
'\0';
printf(
"%s\n", s);
return 0;
}
