TLE 60时间复杂度却没问题
查看原帖
TLE 60时间复杂度却没问题
515891
paper_楼主2023/11/11 11:53
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
char a[N];
int tr[N][26], idx;
int ne[N], depth[N];
int top, sta[N], st[N];
int cnt[N];
void insert(string s) {
	int p = 0;
	for (int i = 0; i < s.size(); i ++ ) {
		int u = s[i] - 'a';
		if (!tr[p][u]) tr[p][u] = ++idx;
		depth[tr[p][u]] = depth[p] + 1;
		p = tr[p][u];
	}
	cnt[p] ++;
}
void D() {
	queue<int> q;
	for (int i = 0; i < 26; i ++ )
		if (tr[0][i]) q.push(tr[0][i]);
	while (q.size()) {
		int p = q.front();q.pop();
		for (int i = 0; i < 26; i ++ ) {
			int u = tr[p][i];
			if (u) {
				ne[u] = tr[ne[p]][i];
				q.push(u);
			}
			else tr[p][i] = tr[ne[p]][i];
		}
	}
}
int main() {
	int n, m;
	cin >> a + 1;
	cin >> m;
	n = strlen(a + 1);
	for (int i = 1; i <= m; i ++ ) {
		string str;
		cin >> str;
		insert(str); 
	}
	D();
	int p = 0;
	for (int i = 1; i <= n; i ++ ) {
		p = tr[p][a[i] - 'a'];
		sta[++top] = a[i] - 'a';
		st[top] = p;
		int j = p;
		while (j) {
			if (cnt[j]) {
				top -= depth[j];
				p = st[top];
				break;
			}
			j = ne[j];
		}
	}
	for (int i = 1; i <= top; i ++ ) putchar(sta[i] + 'a');
	return 0;
}

请指出错误,谢谢

2023/11/11 11:53
加载中...