P3121 [USACO15FEB]审查(AC自动机)

题目：

P3121 [USACO15FEB]审查（黄金）Censoring (Gold)

解析：

多字符串匹配，首先想到AC自动机

建立一个AC自动机

因为有删除和拼接这种操作，考虑用栈维护

顺着文本串匹配的方向走，将经过的节点放入栈中，若匹配到一个模式串，就将这个模式串弹出，从栈顶开始继续走

我们再维护一个pos数组，用来维护trie树中节点对应在文本串中的位置

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, num;

int sta[N], pos[N];

char s[N], t[N];

struct node {

	int fail, end;

	int nx[26];

} e[N];

inline void TrieInsert(char *s) {

	int rt = 0, len = strlen(s);

	for (int i = 0; i < len; ++i) {

		int v = s[i] - 'a';

		if (!e[rt].nx[v]) e[rt].nx[v] = ++num;

		rt = e[rt].nx[v];

	}

	e[rt].end = len;

}

queue<int>q;

inline void GetFail() {

	for (int i = 0; i < 26; ++i) if (e[0].nx[i]) {

			q.push(e[0].nx[i]);

			e[e[0].nx[i]].fail = 0;

		}

	while (!q.empty()) {

		int u = q.front();

		q.pop();

		for (int i = 0; i < 26; ++i) {

			if (e[u].nx[i]) {

				e[e[u].nx[i]].fail = e[e[u].fail].nx[i];

				q.push(e[u].nx[i]);

			} else e[u].nx[i] = e[e[u].fail].nx[i];

		}

	}

}

void query(char *s) {

	int rt = 0, top = 0, len = strlen(s);

	for (int i = 0; i < len; ++i) {

		rt = e[rt].nx[s[i] - 'a'];

		sta[++top] = rt;

		pos[top] = i;

		if (e[rt].end) {

			top -= e[rt].end;

			rt = sta[top];

		}

	}

	for (int i = 1; i <= top; ++i) printf("%c", s[pos[i]]);

	putchar('\n');

}

int main() {

	cin >> t;

	cin >> n;

	for (int i = 1; i <= n; ++i) {

		cin >> s;

		TrieInsert(s);

	}

	GetFail();

	query(t);

	return 0;

}

巴特西

P3121 [USACO15FEB]审查(AC自动机)

题目：

解析：

代码

最新文章

热门文章