求助, 为什么n=1是会TLE?
查看原帖
求助, 为什么n=1是会TLE?
1422328
TaoHongXi楼主2024/10/8 20:27
#include <bits/stdc++.h>
using namespace std;

const int N = 1000100;
int n;
int tr[N][26], cnt[N], idx;
char str[N];
int ne[N];
bool st[N];

void insert(){
	int p = 0;
	for(int i=0;str[i];i++){
		int t = str[i]-'a';
		if(!tr[p][t]) tr[p][t] = ++idx;
		p = tr[p][t];
	}
	cnt[p]++;
}

void build(){
	queue<int> q;
	for(int i=0;i<26;i++){
		if(tr[0][i]){
			q.push(tr[0][i]);
		}
	}
	while(!q.empty()){
		int t = q.front();
		q.pop();
		for(int i=0;i<26;i++){
			int p = tr[t][i];
			if(!p) tr[t][i] = tr[ne[t]][i];
			else{
				ne[p] = tr[ne[t]][i];
				q.push(p);
			}
		}
	}
}
int main(){
	cin>>n;
	
	for(int i=0;i<n;i++){
		scanf("%s",str);
		insert();
	}
	
	build();
	
	scanf("%s",str);
	
	int res = 0;
	for(int i=0, j=0;str[i];i++){
		int t = str[i]-'a';
		j = tr[j][t];
		
		int p = j;
		while(p){
			res+=cnt[p];
			cnt[p] = 0;
			p = ne[p];
		}
	}
	cout<<res<<endl;
	return 0;
}
2024/10/8 20:27
加载中...