Luogu3121 [USACO15FEB]Censoring G

tony102

2021 年 09 月 07 日

1957 次浏览

暂无评论

967字数

题解

[Link](https://www.luogu.com.cn/problem/P3121)

## Sol

这是多串版本的，也许切了这道题，你还能收获它的母题的经验：[Link](https://www.luogu.com.cn/problem/P4824)

首先对与所有的询问串建立 AC 自动机。现在就是要在这个文本串上匹配每一个模式串并且删掉。开一个栈记录当前到了 AC 自动机中的哪一个节点。AC 自动机中的节点都代表了一种匹配的状态，加入这个节点有模式串结束的标记，相当于找到了一个模式串。这个时候把这个栈顶减去该模式串的长度，就可以进行下一次匹配。从而满足题目要求。

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

const int SIZE = 1e6 + 5;

int n, m;
int sta[SIZE], vis[SIZE];
char str[SIZE], txt[SIZE];

namespace ACtrie {
	int t[SIZE][26], fail[SIZE], tag[SIZE], tot;
	void insert(char *s) {
		int N = (int) strlen(s + 1), p = 0;
		for (int i = 1, ch; i <= N; ++ i) {
			ch = s[i] - 'a';
			if (!t[p][ch]) t[p][ch] = ++ tot;
			p = t[p][ch];
		}
		tag[p] = N;
	}

void build() {
		std::queue < int > q;
		for (int i = 0; i < 26; ++ i) {
			if (t[0][i]) q.push(t[0][i]);
		}
		while (!q.empty()) {
			int p = q.front(); q.pop();
			for (int i = 0; i < 26; ++ i) {
				if (t[p][i]) fail[t[p][i]] = t[fail[p]][i], q.push(t[p][i]);
				else t[p][i] = t[fail[p]][i];
			}
		}
	}
	void sol() {
		int p = 0, top = 0, cnt = 0;
		for (int i = 1, ch; i <= n; ++ i) {
			ch = str[i] - 'a', p = t[p][ch], sta[++ top] = p;
			if (tag[p]) vis[i] = tag[p], top = top - tag[p], p = sta[top];
		}
		for (int i = n; i; -- i) {
			if (vis[i]) cnt = cnt + vis[i];
			if (cnt) vis[i] = 1, -- cnt;
		}
	}
}

int main() {
	scanf("%s", str + 1);
	n = (int) strlen(str + 1);
	scanf("%s", txt + 1);
	ACtrie::insert(txt);
	ACtrie::build(); ACtrie::sol();
	for (int i = 1; i <= n; ++ i) {
		if (!vis[i]) putchar(str[i]);
	}
	puts("");
	return 0;
}
```

最后修改：2021 年 09 月 07 日