记录编号	395557	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	Mike的梦境	最终得分	100
用户昵称	再见	是否通过	通过
代码语言	C++	运行时间	2.173 s
提交时间	2017-04-16 18:08:22	内存使用	224.24 MiB

#include <cstdio>
#include <cstdlib>
#include <iostream>

using namespace std;

int n,op,cnt,tot,len[2000010],f[2000010],last[2000010],ch[2000010][26];
string str[200010]; char swa[2000010];

void extend(int la,int c,int w){
	int p=la,id=str[c][w]-'a';
	while(w-len[p]-1<0||str[c][w-len[p]-1]!=str[c][w]) p=f[p];
	if(!ch[p][id]){
		cnt++; ch[p][id]=cnt;
		len[cnt]=len[p]+2;
		if(len[cnt]==1) f[cnt]=2;
		else{
			int q=f[p];
			while(w-len[q]-1<0||str[c][w-len[q]-1]!=str[c][w]) q=f[q];
			f[cnt]=ch[q][id];
			if(!f[cnt]) f[cnt]=2;
		}
	}
	last[c]=ch[p][id];
}

void build(int c){
	last[c]=2; int l=str[c].length();
	for(int i=0;i<l;i++)
		extend(last[c],c,i);
}

void insert(int c){
	int l=str[c].length();
	str[c]+=string(swa);
	int nl=str[c].length();
	for(int i=l;i<nl;i++)
		extend(last[c],c,i);
}

int main(){
	freopen("classmate_easy.in","r",stdin);
	freopen("classmate_easy.out","w",stdout);
	scanf("%d",&n);
	len[1]=-1; len[2]=0;
	f[1]=2; f[2]=1;
	last[0]=cnt=2;
	for(int i=1;i<=n;i++){
		scanf("%d",&op);
		if(op==1){
			scanf("%s",swa);
			str[i]=string(swa);
			build(i);
		}
		if(op==2){
			int k;
			scanf("%d%s",&k,swa);
			insert(k);
		}
		printf("%d\n",cnt-2);
	}
	return 0;
}