TLE求调
查看原帖
TLE求调
1191286
So_so楼主2025/8/29 21:04
#include <bits/stdc++.h>
using namespace std;
#define N 2000005
#define SIZE 2000005
#define LEN 2000005
int n;

struct Node {
	int son[26];
	int ans;
	int fail;
	int du;
	int idx;
	vector<int> ids;
	void init() {
		memset(son, 0, sizeof(son));
		ans = fail = idx = 0;
	}
} tr[SIZE];

int tot;
int ans[N], pidx;
bool vis[N];

void insert(char s[], int id) {
	int u = 0;
	for (int i = 1; s[i]; i++) {
		int c = s[i] - 'a';
		if (!tr[u].son[c]) {
			tr[u].son[c] = ++tot;
			tr[tot].init();
		}
		u = tr[u].son[c];
	}
	tr[u].ids.push_back(id);
}

void build() {
	queue<int> q;
	for (int i = 0; i < 26; i++) {
		if (tr[0].son[i]) {
			q.push(tr[0].son[i]);
		}
	}

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

void query(char t[]) {
	int u = 0;
	for (int i = 1; t[i]; i++) {
		int c = t[i] - 'a';
		u = tr[u].son[c];
		for (int tmp = u; tmp; tmp = tr[tmp].fail) {
			for (int id : tr[tmp].ids) {
				vis[id] = true;
			}
		}
	}
}

char s[LEN];
int idx[N];

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%s", s + 1);
		insert(s, i);
		ans[i] = 0;
	}
	build();
	scanf("%s", s + 1);
	query(s);
	int res = 0;
	for (int i = 1; i <= n; i++) {
		if (vis[i]) {
			res++;
		}
	}
	printf("%d", res);
	return 0;
}

TLE50 求调

2025/8/29 21:04
加载中...