AC自动机MLE求条
查看原帖
AC自动机MLE求条
608273
___PatrickChen___楼主2024/10/9 14:02
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

using ll = long long;

const ll N = 1e6 + 5;

int n, ch[N][30], flag[N], fail[N], idx;
string s[N];
struct node {
	int cnt, id;
} ans[N];
int getnum(char c) {
	return c - 'a';
}
void insert(string s, int id) {
	int p = 0, len = s.size();
	for (int i = 0; i < len; ++i) {
		int c = getnum(s[i]);
		if (!ch[p][c]) ch[p][c] = ++idx;
		p = ch[p][c];
	}
	flag[p] = id;
}
void get_fail() {
	queue<int>q;
	for (int i = 0; i < 26; ++i) {
		if (ch[0][i]) {
			int u = ch[0][i];
			q.push(u);
		}
	}
	while (q.size()) {
		int u = q.front();
		q.pop();
		for (int i = 0; i < 26; ++i) {
			if (ch[u][i]) {
				fail[ch[u][i]] = ch[fail[u]][i];
				q.push(ch[u][i]);
			}
			else ch[u][i] = ch[fail[u]][i];
		}
	}
}
void query(string s) {
	int p = 0, len = s.size();
	for (int i = 0; i < len; ++i) {
		int c = getnum(s[i]);
		p = ch[p][c];
		for (int j = p; j; j = fail[j]) ++ans[flag[j]].cnt;
	}
}

void init() {
	for (int i = 1; i <= n; ++i) {
		memset(ch[i], 0, sizeof ch[i]);
		fail[i] = 0;
		flag[i] = 0;
	}
}

void solve() {
	init();
	for (int i = 1; i <= n; ++i) {
		cin >> s[i];
		insert(s[i], i);
		ans[i].cnt = 0;
		ans[i].id = i;
	}
	get_fail();
	cin >> s[0];
	query(s[0]);
	sort(ans + 1, ans + n + 1, [](node x, node y) {
		return x.cnt > y.cnt;
	});
	cout << ans[1].cnt << endl;
	cout << s[ans[1].id] << endl;
	for (int i = 2; i <= n; ++i) {
		if (ans[i].cnt == ans[1].cnt) cout << s[ans[i].id] << endl;
		else break;
	}
	cin >> n;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n;
	while (n) solve();
	return 0;
}
2024/10/9 14:02
加载中...