题目描述

这题有一个弱化版本的，是只有一个单词，然后要求你在一个article里面把这个单词删掉
比如article = “adeummooooeyreu”， 然后单词是”moo”
删除之后就应该是”adeueyreu”，删掉了一个moo之后会出现另外一个moo要接着删
这个弱化版本的就是用KMP + 栈来做，那强化版本的多个单词肯定就是用AC自动机 + 栈了嘛
我的代码是java写的，最后一个数据怎么都过不了，用cpp来写的话说不定可以过掉

样例

请自行参考Acwing1284

AC自动机 + 栈

Java 代码

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Acwing1284￥ {
    /*
    这题其实就是给你一个字符串str，然后再给你多个字符串words[m]，问你在str里面把这些words
    全都删掉之后还剩下什么东西
    比如
    begintheescapexecutionatthebreakofdawn
    2
    escape
    execution
    输出就是beginthatthebreakofdawn
    很明显你删掉了某个单词有可能导致另外一个单词的出现，比如str = aabbb
    然后words是ab和abb，你删掉ab之后就发现只剩abb了，然后abb又要接着删
    我不知道能不能成功啊，赌一把吧，2021年6月3日22:50:15

     */
    static int N = 100010, n = 2010;
    static int trie[][] = new int[N][30], wordsnumber,
            index = 0,next[] = new int[N], floor[] = new int[N];
    static boolean iswordsend[] = new boolean[N];
    static int q[] = new int[N], head = 0, tail = -1;
    static int stackofnumber[] = new int[N], pointer = -1;
    static StringBuilder sb = new StringBuilder();
    static int stackofjump[] = new int[N];
    // 所有的字符串里面只有小写字母
    static String article;
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void insert(String word){
        int p = 0;
        int depth = 0;
        for(int i = 0 ; i < word.length(); i ++ ){
            depth ++ ;
            int c = word.charAt(i) - 'a' + 1;
            if(trie[p][c] == 0){
                trie[p][c] = ++ index;
            }
            p = trie[p][c];
            floor[p] = depth;
        }
        iswordsend[p] = true;
        // 单词结尾记录一下
    }
    public static void buildAC(){
        next[0] = - 1;
        for(int i = 1; i <= 26; i ++ ){
            if(trie[0][i] == 0 ) continue;
            q[++ tail] = trie[0][i];
            // 第一层的next全都指向根节点0的，所以直接入队，都已经算好了
        }
        while(tail - head + 1 > 0){
            int father = q[head ++ ];
            for(int i = 1; i <= 26; i ++ ){
                int child = trie[father][i];
                if(child == 0) continue;
                int p = next[father];
                while(p >= 0 && trie[p][i] == 0) p = next[p];
                if(p == -1) next[child] = 0;
                else next[child] = trie[p][i];
                q[++ tail] = child;
            }
        }
    }
    public static void main(String args[])throws Exception{
        article = reader.readLine();
        String t = reader.readLine();
        wordsnumber = Integer.parseInt(t);
        for(int i = 1; i <= wordsnumber; i ++ ){
            String word = reader.readLine();
            insert(word);
        }
        buildAC();
        int len = article.length();
        article = " " + article;
        stackofnumber[++ pointer] = ' ' - 'a' + 1;
        // stackofnumber存的是article里面的一个一个字母
        // 之后如果要删的话也是从这个栈里面慢慢弹出来
        stackofjump[pointer] = 0;
        // stackofjump[i]存的是如果i + 1 ~ i + k这样在i后面的一段是一个单词的话
        // 我的把这一段删掉之后会继续读入第i + k + 1个字符
        // stackofjump[i]存的就是这个第i + k + 1个字符应该去跟trie里面的哪个节点的孩子匹配
        // 所以一开始的话，stackofnumber[0]存的是article[0]就当成是空串好了
        // 然后是stackofjump[0]，对应的i是0，k是0，这样才是第1 ~ 0一个空串嘛
        // 接下来要读入的是第0 + 0 + 1个字符，他应该去跟trie里面的root的孩子去匹配
        // 所以stackofjump[0] = 0
        for(int i = 1; i <= len ; i ++ ){
            int father = stackofjump[pointer ++ ];
            int p = father;
            int c = article.charAt(i) - 'a' + 1;
            stackofnumber[pointer] = c;
            sb.append(article.charAt(i));
            while(p >= 0 && trie[p][c] == 0) p = next[p];
            if(p == - 1) stackofjump[pointer] = 0;
            else stackofjump[pointer] = trie[p][c];
            if(iswordsend[stackofjump[pointer]]) {
                sb.delete(pointer - floor[stackofjump[pointer]] ,pointer );
                pointer -= floor[stackofjump[pointer]];

            }
                // 如果刚进来的这个是一个单词的结尾，那么就开始删除吧

        }
        writer.write(sb.toString());
        //System.out.println(sb.toString());
//        for(int i = 1; i <= pointer; i ++ )writer.write((char)(stackofnumber[i] + 'a' - 1));
         writer.flush();
    }
}