测评记录

提供一种做法，感觉能卡到$O(n^2)$(?我乱说的)，是不是数据太水的原因

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
const int N=5e5+5;
struct node{
	int last;
	string s;
}f[N];
int check(int st,string str){
	int now=st,ans=0;
	while(now!=-1){
		int s=str.find(f[now].s,0);
		while(f[now].s!=""&&s!=string::npos){
			s=str.find(f[now].s,s+1);
			ans++;
		}
		now=f[now].last;
	}
	return ans;
}
int q;
int main()
{
	scanf("%d",&q);
	f[0].last=-1;
	for(int i=1;i<=q;i++){
		int op,hoc;
		string str;
		scanf("%d%d",&op,&hoc);
		cin>>str;
		if(op==1){
			f[i].last=hoc;
			f[i].s=str;
		}
		if(op==2){
			f[i].last=hoc;
			printf("%d\n",check(i,str));
		}
	}
}