TLE 求助
查看原帖
TLE 求助
688783
SilverLi楼主2023/8/19 08:33
#include <iostream>
#include <cstring>
#define root 0
#define k s[i] - 'a' + 1
using namespace std;
constexpr int N = 1e6 + 5;
int n;
char s[N];
// Fail
int nxt[N];
// Trie
int w[N], f[N][30], cnt;
inline int getFail(int fa, int x) {
	int p = nxt[fa];
	if (f[p][x])
		return f[p][x];
	return 0;
}
inline void insert(char *s) {
	int p = 0, len = strlen(s);
	for (int i = 0; i < len; ++i) {
		if (!f[p][k])
			f[p][k] = ++cnt;
		int last = p;
		p = f[p][k];
		nxt[p] = getFail(last, k);
	}
	++w[p];
}
inline int solve(char *s) {
	int p = 0, ans = 0, len = strlen(s);
	for (int i = 0; i < len; ++i) {
		//printf("IN %d %d\n", i, k);
		while (!f[p][k] && p != root)
			p = nxt[p];
		if (f[p][k])
			p = f[p][k];
		//printf("%d\n", p);
		int tmp = p;
		while (tmp != root) {
			if (w[tmp]) {
				ans += w[tmp];
				w[tmp] = 0;
			}
			tmp = nxt[tmp];
		}
	}
	return ans;
}
signed main() {
	cin >> n;
	while (n--) {
		cin >> s;
		insert(s);
	}
	cin >> s;
	cout << solve(s);
	return 0;
}
2023/8/19 08:33
加载中...