萌新求助关于 #2 TLE 了 qAq
查看原帖
萌新求助关于 #2 TLE 了 qAq
298549
SIXIANG32楼主2022/10/5 22:31
//SIXIANG
#include <iostream>
#include <queue>
#include <string>
#define MAXN 1000000
#define QWQ cout << "QWQ" << endl;
using namespace std;
string str[MAXN + 10], txt;
int tot = 0, trie[MAXN + 10][30], fail[MAXN + 10], cnt[MAXN + 10], ind[MAXN + 10];
void Insert(string str, int id) {
	int now = 0;
	for(int p = 0; p < str.size(); p++) {
		int c = str[p] - 'a' + 1;
		if(!trie[now][c]) trie[now][c] = ++tot;
		now = trie[now][c];
	}
	cnt[now]++;
	ind[now] = id;
}
void Build() {
	queue <int> que;
	for(int p = 1; p <= 26; p++)
		if(trie[0][p]) que.push(p); 
	
	while(!que.empty()) {
		int w = que.front(); que.pop();
		for(int c = 1; c <= 26; c++) {
			int x = trie[w][c];
			if(!x) {
				trie[w][c] = trie[fail[w]][c];
				continue;
			}
			fail[x] = trie[fail[w]][c];
			que.push(x);
		}
	}
}

int Query(string txt) { 
	int ans = 0;
	for(int p = 0; p < txt.size(); p++) {
		int c = txt[p] - 'a' + 1;
		for(int now = trie[p][c]; cnt[now] != -1 && now; now = fail[now]) {
			ans += cnt[now];
			cnt[now] = -1;
		}
	}
	return ans;
}
int main() {
    ios::sync_with_stdio(0);
	int n; cin >> n;
	for(int p = 1; p <= n; p++)
		cin >> str[p], Insert(str[p], p);
	Build();
	cin >> txt;
	cout << Query(txt) << "\n";
}

是不是写假了啊,求助巨佬 qaq

2022/10/5 22:31
加载中...