如果你 MLE on #8 #9 #10

或许可以检查一下对一开始阿狸输入的字符串的处理。

例如，如果你这样写：

void Split()
	{
		for(int i=0;i<F.size();i++) // F 为第一行输入的字符串
		{
			if(F[i]=='B') top--;
			else if(F[i]=='P') 
			{
				len++;
				for(int j=1;j<=top;j++) s[len]+=S[j]; // 复制当前打印的字符串
			}
			else S[++top]=F[i];
		}
	}
//  随后将 s[1-len] 插入 Trie 树

那么你会 MLE 最后三个点。问题在于字符串数组 $s[]$。

如果你这样写：

void Insert(int len,int id)
	{
		int p=0;
		for(int i=1;i<=len;i++)
		{
			if(!G[p][s[i]-'a'+1]) G[p][s[i]-'a'+1]=++tot,tr[p].push_back(tot);
			p=G[p][s[i]-'a'+1];
		}
		End[p]=id; fEnd[id]=p;
	}
void Split()
	{
		for(int i=0;i<F.size();i++)
		{
			if(F[i]=='B') top--;
			else if(F[i]=='P') A.Insert(top,(++len));
			else s[++top]=F[i];
		}
	}
// 不新开字符串数组复制，而在插入时调用栈 s

将会 TLE 最后三个点。原因在于可以构造第一行字符串如 aaaaaaaPPPPPPP 的形式将插入的复杂度卡到 $O(n^2),n\le 5\times 10^4$。

综上所述，我们应该在处理 $F$ 数组的同时进行插入，如：

void Split()
	{
		int p=0;
		for(int i=0;i<F.size();i++)
		{
			if(F[i]=='B') p=fa[p];
			else if(F[i]=='P') End[p]=++len,fEnd[len]=p;
			else
			{
				if(!G[p][F[i]-'a'+1]) G[p][F[i]-'a'+1]=++tot,tr[p].push_back(tot);
				fa[G[p][F[i]-'a'+1]]=p;
				p=G[p][F[i]-'a'+1];
			}
		}
	}

这样可以通过本题，提交记录