信息学奥赛一本通T1481-Censoring-题解（C++代码）

解题思路:
        

        AC自动机。使用栈保存匹配过程中的信息，若匹配成功弹出模式串，最后栈剩下的就是匹配完剩下的字符。

参考代码:

constexpr auto Inf = 0X3F3F3F3F;
#ifndef LOCAL
	#include <bits/stdc++.h>
#endif

typedef unsigned long long LL;
using namespace std;

namespace IO {
	inline LL read() {
		LL o = 0, f = 1; char c = getchar();
		while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
		while (c > '/' && c < ':') { o = o * 10 + c - '0'; c = getchar(); }
		return o * f;
	}
	inline char recd() {
		char o; while ((o = getchar()) < '0' || o > '9'); return o;
	}
	inline double reod() {
		double o = read(), f = 1; char c;
		while ((c = getchar()) > '/' && c < ':') o += (c - '0') / (f *= 10);
		return o;
	}
}
using namespace IO;

const int SIZE = 1E5 + 7, Mod = (1E9 + 7, 998244353);

struct Aho {
	struct Node {
		int sub[26]; int fail, g;
	} Node[SIZE << 2]; int Ind;

	void clear() {
		for (int pos = 0; pos <= Ind; pos++) {
			for (int e = 0; e < 26; e++) Node[pos].sub[e] = 0;
			Node[pos].fail = Node[pos].g = 0;
		} Ind = 0;
	}

	int Ins(char S[], int g) {
		int now = 0;
		for (int pos = 1; S[pos]; pos++) {
			if (!Node[now].sub[S[pos] - 'a']) Node[now].sub[S[pos] - 'a'] = ++Ind;
			now = Node[now].sub[S[pos] - 'a'];
		} Node[now].g = g; return now;
	}

	void BUILD() {
		queue<int> que;  
		for (int pos = 0; pos < 26; pos++)
			if (Node[0].sub[pos])
				Node[Node[0].sub[pos]].fail = 0, que.push(Node[0].sub[pos]);
		while (!que.empty()) {
			int now = que.front(); que.pop();
			for (int pos = 0; pos < 26; pos++) {
				if (Node[now].sub[pos])
					Node[Node[now].sub[pos]].fail = Node[Node[now].fail].sub[pos], que.push(Node[now].sub[pos]);
				else
					Node[now].sub[pos] = Node[Node[now].fail].sub[pos];
			}
		}
	} 
} Aho;

char T[SIZE], S[SIZE]; int stacks[SIZE], top, back[SIZE];

int main() {
	scanf("%s", T + 1);
	int N = read();
	for (int pos = 1; pos <= N; pos++) scanf("%s", S + 1), Aho.Ins(S, strlen(S + 1));
	Aho.BUILD();

	int now = 0;
	for (int pos = 1; T[pos]; pos++) {
		now = Aho.Node[now].sub[T[pos] - 'a'];
		back[pos] = now, stacks[++top] = pos;
		if (Aho.Node[now].g) {
			top -= Aho.Node[now].g;
			now = back[stacks[top]];
		}
	}
	for (int pos = 1; pos <= top; pos++) printf("%c", T[stacks[pos]]);
}