求助,MLE on #9
查看原帖
求助,MLE on #9
359614
Forever1507楼主2022/9/4 21:50
#include<bits/stdc++.h>
using namespace std;
const int base=131;
#define ull unsigned long long
ull hsh[300005]; 
int n,i,pos;
long long ans;
ull fac[100005],_;
struct node{
	int v;
	string s;
}; 
string sss;
vector<node>nbr[100005];
void work(string s){
	hsh[0]=s[0]-'a';
	for(i=1;i<s.size();++i){
		hsh[i]=hsh[i-1]*base+s[i]-'a';
	}
	return;
}
ull calc(int l,int r){
	if(l==0)return hsh[r];
	return hsh[r]-hsh[l-1]*fac[r-l+1];
}
void dfs(int cur,int fa,string s){
	for(auto to:nbr[cur]){
		if(to.v==fa)continue;
		string ss=s+to.s;
		work(ss);
		if(ss.size()>=sss.size()){
			for(pos=s.size();pos<ss.size();++pos){
				if((int)(pos-sss.size()+1)<0)continue;
				if(calc(pos-sss.size()+1,pos)==_){
					ans++;
//					cout<<to.v<<' '<<pos-ss.size()+1<<'\n';
				}
			}
		}
		dfs(to.v,cur,ss);
	}
}
signed main(){
	cin>>n;
	fac[0]=1;fac[1]=base;
	int fa;
	for(i=2;i<=n;++i){
		cin>>fa>>sss;
		nbr[fa].push_back((node){i,sss});
		fac[i]=fac[i-1]*base;
	}
	cin>>sss;
	for(i=0;i<sss.size();++i)_=_*base+sss[i]-'a';
	dfs(1,0,"");
	cout<<ans;
	return 0;
}

2022/9/4 21:50
加载中...