计蒜客 – 蒜厂工作手册

蒜厂工作手册，你听说过么？蒜头君把蒜厂工作手册全部摘抄了下来并把它变成了一个长度不超过 $10^5$ 的字符串 $S$，蒜头君还有一个包含 $n$ 个单词的列表，列表里的 $n$ 个单词记为 $t_1\cdots t_N$。他希望从 $S$ 中删除这些单词。

蒜头君每次在 $S$ 中找到第一个出现的列表中的单词，然后从 $S$ 中删除这个单词。他重复这个操作直到 $S$ 中没有列表里的单词为止。需要注意的是删除一个单词后，后面的紧跟着的字符和前面的字符连接起来可能再次出现列表中出现的单词。并且蒜头君注意到列表中的单词不会出现一个单词是另一个单词子串的情况。

请你帮助蒜头君输出删除后的 $S$。

输入格式

第一行输入一个字符串 $S(1\leq |S| \leq 10^5 )$。

第二行输入一个整数 $N(1\leq N \leq 2000)$。

接下来的 $N$ 行，每行输入一个字符串，第 $i$ 行的字符串是 $t_i$。

$N$ 个字符串的长度和小于 $10^5$。注意：输入的字符串仅包含小写字母。

oorjskorzorzzooorzrzrzr
2
orz
jsk

输出格式

答案输出一行，输出操作后的 $S$。

or

这道题的 main 函数非常简单，首先初始化 AC 自动机，然后读入所有的单词，insert()，最后 build() 即可。查找单词自然有 search() 来完成。

int main() {
    // 构造 AC 自动机
    auto ac = new AC_Automaton();
    ac->clear();
    // 给定的文章，下标从 1 开始
    char* t = (char*)malloc(sizeof(char) * MAXN);
    scanf("%s", t + 1);
    int n;
    scanf("%d", &n);
    // 读入单词，加入前缀树
    char* s = (char*)malloc(sizeof(char) * MAXN);
    for (int i = 0; i < n; i++) {
        // 字符串下标从 1 开始
        scanf("%s", s + 1);
        ac->insert(s);
    }
    // 根据前缀树中的单词构造失败指针，即构造字典
    ac->build();
    // TODO answer
    return 0;
}

现在的问题是，如何模拟字符串被删除的过程。

不可能每次都是真的去操作一个字符串，移动、拼接，也不可能每次生成一个新的字符串。

有一个技巧非常常用，我们可以利用键盘上退格键（Backspace）的原理，来用一个栈来模拟这件事情。

比如说我现在在打字，照着工作手册，一个字母一个字母地输入，第一句话是 HelloWorld，我就先输入一个 H，然后是 e，然后是 l……这个过程就是入栈的过程，每次往栈中压一个字母。

突然我输入到 o 的时候，此时栈顶元素是 o，栈中已经有的字符串是 Hello，我发现 llo 是单词手册中需要我删除的一个单词，这是第一次出现这个单词，所以我在第一时间发现了这个问题（输入到 o 之前我并不知道这件事），所以我要把这个单词删除，我按了 3 次退格键，相当于做了 3 次出栈操作，此时栈顶元素变成 e。

我继续往后输入，输入 W，然后发现 eW 也是一个需要删除的单词，所以我又做了 2 次出栈。

从上面的过程可以发现，这个栈完全满足题目的要求，删除字符串后，后面的紧跟着的字符和前面的字符连接起来可能再次出现列表中出现的单词，也可以顺利解决。

// ans 为字符串，cursor 为当前光标的位置
char* ans = (char*)malloc(sizeof(char) * MAXN);
int cursor = 0;
// stack 为模拟的栈，其每一个元素记录一个前缀树结点的编号，top 是栈顶指针
int* stack = (int*)_malloca(sizeof(int) * MAXN);
int top = 0;
// 初始从前缀树根节点开始
int p = 0;
// 注意字符串下标从 1 开始
int l = strlen(ch + 1);
for (int i = 0; i < l; i++) {
    ans[cursor] = ch[i]; // 输入当前字符
    cursor++; // 光标移动一位
    p = child[p][ch[i] - 'a']; // 前缀树节点往后移动一个，到该字符
    stack[top] = p; // 保存进栈，以便后面处理
    top++; // 栈顶指针
    if (?) { // TODO
        int length = ?; // 需要删除的单词的长度 // TODO
        cursor -= length; // 回退那么多个长度
        top -= length; // 回退那么多个长度
        p = stack[top - 1]; // 取出当前的栈顶元素
    }
}

上面这段代码就是模拟栈的过程，应该很好理解。

接下来就要考虑，就是我们拿到栈中的结点 p，可以干什么，可以利用哪些东西，来求出那个 length。

只需要把这个问号填了，这道题就解决了。

首先我们需要知道每一个单词的长度，即对于结点 p，len[p] 记录了字典中到这个结点为止的单词的长度。这个只需要在 insert() 的时候记录一下就可以了。

另外，由于本题不像上一题一样还需要记录个数，所以可以把 sta[] 当做 boolean[] 来用，直接设置为 true，不做 sta[p]++ 了。

那么，这里的 if 就可以是：如果 sta[p] 是 true，说明字典中存在这个单词，要进行删除操作，于是模拟 Backspace 的过程，将光标和栈顶指针后移。

if (sta[p]) { // sta[p] 表示以结点 p 为路径的字符串是不是存在，如果存在，那么按照题目意思就要删除它，模拟 Backspace 的过程
    int length = len[p]; // 需要删除的单词的长度
    cursor -= length; // 回退那么多个长度
    top -= length; // 回退那么多个长度
    p = stack[top - 1]; // 取出当前的栈顶元素
}

只需要把这段 if 贴在上面那段代码的 //TODO 位置，题目就完成了。

其他 AC 自动机的函数直接用模板，不需要修改，最后输出 printf("%s\n", ac->solve(t))。

#include <bits/stdc++.h>

const int MAXC = 26;
const int MAXN = 100007;

using namespace std;

int child[MAXN][MAXC], fail[MAXN], sta[MAXN], Q[MAXN];
int tot;
int len[MAXN];

/**
 * AC 自动机
 */
struct AC_Automaton {

    /**
     * 清空
     */
    void clear() {
        memset(child, 255, sizeof(child));
        memset(fail, 0, sizeof(fail));
        tot = 0;
        memset(sta, 0, sizeof(sta));
    }

    /**
     * 插入单词
     * @param ch 单词，该单词下标从 1 开始
     */
    void insert(char *ch) {
        int p = 0, l = strlen(ch + 1);
        for (int i = 1; i <= l; i++) {
            if (child[p][ch[i] - 'a'] == -1) child[p][ch[i] - 'a'] = ++tot;
            p = child[p][ch[i] - 'a'];
        }
        sta[p] = 1; // 以结点 p 的字符串是否存在，由于本题只需要是否存在，设置 true 就好了，像上一题还需要统计个数，可以改为 sta[p]++，表示有多少个
        len[p] = l; // 结点 p 的字符串的长度
    }

    /**
     * 对插入了单词的前缀树构造失败指针
     */
    void build() {
        int l = 0, r = 0;
        for (int i = 0; i < MAXC; i++)
            if (child[0][i] == -1)
                child[0][i] = 0;
            else
                Q[++r] = child[0][i];
        while (l < r) {
            int p = Q[++l];
            for (int i = 0; i < MAXC; i++)
                if (child[p][i] == -1)
                    child[p][i] = child[fail[p]][i];
                else {
                    fail[child[p][i]] = child[fail[p]][i];
                    Q[++r] = child[p][i];
                }
        }
    }

    /**
     * 给定一个字符串，删除所有存在在字典中的单词，并返回
     * @param ch 给定的字符串，该字符串下标从 1 开始
     * @return 操作完成后的字符串
     */
    char *solve(char *ch) {
        // ans 为字符串，cursor 为当前光标的位置
        char *ans = (char *) malloc(sizeof(char) * MAXN);
        int cursor = 0;
        // stack 为模拟的栈，其每一个元素记录一个前缀树结点的编号，top 是栈顶指针
        int *stack = (int *) malloc(sizeof(int) * MAXN);
        int top = 0;
        // 初始从前缀树根节点开始
        int p = 0;
        // 注意字符串下标从 1 开始
        int l = strlen(ch + 1);
        for (int i = 1; i <= l; i++) {
            ans[cursor] = ch[i]; // 输入当前字符
            cursor++; // 光标移动一位
            p = child[p][ch[i] - 'a']; // 前缀树节点往后移动一个，到该字符
            stack[top] = p; // 保存进栈，以便后面处理
            top++; // 栈顶指针
            if (sta[p]) { // sta[p] 表示以结点 p 为路径的字符串是不是存在，如果存在，那么按照题目意思就要删除它，模拟 Backspace 的过程
                int length = len[p]; // 需要删除的单词的长度
                cursor -= length; // 回退那么多个长度
                top -= length; // 回退那么多个长度
                p = stack[top - 1]; // 取出当前的栈顶元素
            }
        }
        ans[cursor] = '\0';
        return ans;
    }
} T;

int main() {
//    freopen("in.txt", "r", stdin);
    // 构造 AC 自动机
    auto ac = new AC_Automaton();
    ac->clear();
    // 给定的文章，下标从 1 开始
    char *t = (char *) malloc(sizeof(char) * MAXN);
    scanf("%s", t + 1);
    int n;
    scanf("%d", &n);
    // 读入单词，加入前缀树
    char *s = (char *) malloc(sizeof(char) * MAXN);
    for (int i = 0; i < n; i++) {
        // 字符串下标从 1 开始
        scanf("%s", s + 1);
        ac->insert(s);
    }
    // 根据前缀树中的单词构造失败指针，即构造字典
    ac->build();
    // 执行操作，输出结果
    printf("%s\n", ac->solve(t));
    return 0;
}