TLE求调,已过样例
查看原帖
TLE求调,已过样例
1153557
Brokwind楼主2025/1/26 11:12
#include<iostream>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<bitset>
#include<set>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<string>
#include<unordered_map>
#define qi queue<int>
#define pii pair<int,int>
#define pll pair<long long,long long>
#define mpii map<int,int>
#define mpll map<long long,long long>
#define mst memset
#define ll long long
#define db double
#define ldb long double
#define bst bitset
#define vec vector
#define szf sizeof
#define inf 0x3f3f3f3f
#define dq deque
using namespace std;

inline int read(){
    ll x=0,f=1;
    char ch=getchar();
    while(isdigit(ch)==0 && ch!='-')ch=getchar();
    if(ch=='-')f=-1,ch=getchar();
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}

inline void write(int x){
    int f=0;char ch[40];
    if(!x){fputs("0\n",stdout);return;}
    if(x<0){putchar('-');x=-x;}
    while(x)ch[++f]=x%10+'0',x/=10;
    while(f)putchar(ch[f--]);
    putchar('\n');
}

const int MAXN=1e7+10;

struct Tree{
	char val;
	int to[26],fail,cnt,num;
}t[MAXN];

int tot,n,head[MAXN],num;
char s[MAXN],T[MAXN];

struct Edge{
	int to,ne;
}e[MAXN];

void adde(int u,int v){
	num++;
	e[num].to=v,e[num].ne=head[u],head[u]=num;
	return;
}

void adds(char S[]){
	int len=strlen(S);
	int x=0;
	for(int i=0;i<len;i++){
		if(t[x].to[S[i]-'a']){
			x=t[x].to[S[i]-'a'];
		}else{
			tot++;
			t[tot].val=S[i];
			t[x].to[S[i]-'a']=tot;
			x=tot;
		}
	}
	t[x].cnt+=1;
	return;
}

void build(){
	qi q;
	for(int i=0;i<26;i++){
		if(t[0].to[i]){
			q.push(t[0].to[i]);
			adde(0,t[0].to[i]);
		}
	}
	while(q.size()){
		int x=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			int v=t[x].to[i];
			int j=t[x].fail;
			if(v){
				t[v].fail=t[t[x].fail].to[i];
				adde(t[v].fail,v);
				q.push(v);
			}else{
				t[x].to[i]=t[t[x].fail].to[i];
			}
		}
	}
	return;
}

int dfs(int x){
	int re=0;
	for(int i=head[x];i;i=e[i].ne){
		int v=e[i].to;
		re+=dfs(v);
		t[x].num+=t[v].num;
	}
	if(t[x].num){
		re+=t[x].cnt;
	}
	return re;
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("\n%s",s);
		adds(s);
	}
	build();
	scanf("\n%s",T+1);
	for(int i=1,j=0;i<=strlen(T+1);i++){
		j=t[j].to[T[i]-'a'];
		t[j].num++;
	}
	cout<<dfs(0)<<endl;

    return 0;
}
2025/1/26 11:12
加载中...