社区讨论

#2WA求调

P3808AC 自动机(简单版)参与者 6已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@lo2xhvhp
此快照首次捕获于
2023/10/23 21:23
2 年前
此快照最后确认于
2023/10/23 21:23
2 年前
查看原帖
rt
CPP
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 0721;
int tr[N][26], ed[N], fail[N], tot;

void insert(string s) {
	int u = 0;
	for (int i = 0; i < s.length(); ++i) {
		if (!tr[u][s[i] - 'a'])
			tr[u][s[i] - 'a'] = ++tot;
		u = tr[u][s[i] - 'a'];
	}
	++ed[u];
}

queue<int> q;
void build(void) {
	for (int i = 0; i < 26; ++i) {
		if (tr[0][i]) q.push(tr[0][i]);
	}
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = 0; i < 26; ++i) {
			if (tr[u][i]) {
				fail[tr[u][i]] = tr[fail[u]][i];
				q.push(tr[u][i]);
			} else
				tr[u][i] = tr[fail[u]][i];
		}
	}
}

int query(string s) {
	int res = 0, u = 0;
	for (int i = 0; i < s.length(); ++i) {
		u = tr[u][s[i] - 'a'];
		for (int j = u; j && ed[j] != -1; j = fail[j]) {
			res += ed[j];
			ed[j] = -1;
		}
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		string s;
		cin >> s;
		insert(s);
	}
	
	string s;
	cin >> s;
	cout << query(s);
	
	return 0;
}

回复

6 条回复,欢迎继续交流。

正在加载回复...