A 了,但求问
查看原帖
A 了,但求问
814145
XXh0919楼主2025/7/22 10:42

我看别的帖子说数组开大了就不会 MLE,但是我把数组开小了,还用了 memset 反而 A 了,为什么?

我的提交记录

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef int itn;
const int N = 2e4 + 15, M = 160, mod = 1e9 + 7;

#define pi pair<itn,int>
#define fro for
#define sizoef sizeof

int n;
int trie[N][26], fail[N], idx;
int cnt[N], sum[N];
string t;

void insert(string s, int id) {
	int p = 0, len = s.size();
	for (int i = 0; i < len; ++ i) {
		int c = s[i] - 'a';
		if (!trie[p][c]) trie[p][c] = ++ idx;
		p = trie[p][c];
	}
	cnt[p] = id;
}

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

void solve(string s) {
	int p = 0, len = s.size();
	for (int i = 0; i < len; ++ i) {
		int c = s[i] - 'a';
		p = trie[p][c];
		for (int j = p; j; j = fail[j]) {
			if (cnt[j]) ++ sum[cnt[j]];
		}
	}
}

int main() {
	while (1) {
		vector <string> s;
		scanf ("%d", &n);
		if (n == 0) break;
		memset (trie, 0, sizeof trie);
		memset (sum, 0, sizeof sum);
		memset (cnt, 0, sizoef cnt);
		idx = 0;
		s.push_back("");
		for (int i = 1; i <= n; ++ i) {
			string str;
			cin >> str;
			insert (str, i);
			s.push_back (str);
		}
		cin >> t;
		bfs();
		solve(t);
		int ans = -0x3f3f3f3f;
		vector <string> Ans;
		for (int i = 1; i <= n; ++ i) ans = max (ans, sum[i]);
		for (int i = 1; i <= n; ++ i) {
			if (sum[i] == ans) Ans.push_back(s[i]);
		}
		printf ("%d\n", ans);
		for (string str : Ans) {
			for (int i = 0; i < str.size(); ++ i) {
				putchar (str[i]);
			}
			puts ("");
		}
	}
	return 0;
}
2025/7/22 10:42
加载中...