以下代码： https://www.luogu.com.cn/record/175726038

是在 AC 自动机 fail 树上先求出祖先中的上一个 end 然后暴力跳并标记，理论复杂度是 $\mathcal O(n)$ 的。总共 $\mathcal O(nq)$，可以通过，建议加强数据。

(太菜了不会造数据)

附录：代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,Q=2e6+5;
//SIZEOF SegT+Trie==312MB
string s[N];int n,q;
namespace ACAM{
	struct Trie{
		int son[26],fail,include,end;
		bool vis;
	}t[Q];
	int tot,rt,endpos[N];
	void Insert(string str,int id){
		int cur=rt;
		for(char c:str){
			if(!t[cur].son[c-'a'])
				t[cur].son[c-'a']=++tot;
			cur=t[cur].son[c-'a'];
		}
		t[cur].end=1,endpos[id]=cur;
	}
	vector<int> e[Q];
	void BuildFail(){
		queue<int> q;
		for(int i=0;i<26;i++){
			if(t[rt].son[i]) q.push(t[rt].son[i]),e[rt].push_back(t[rt].son[i]);
		}
		while(!q.empty()){
			int ln=q.front();q.pop();
			for(int i=0;i<26;i++){
				if(t[ln].son[i])
					t[t[ln].son[i]].fail=t[t[ln].fail].son[i],
					q.push(t[ln].son[i]),//printf("%d FAIL TO %d\n",t[ln].son[i],t[t[ln].son[i]].fail),
					e[t[t[ln].son[i]].fail].push_back(t[ln].son[i]);
				else t[ln].son[i]=t[t[ln].fail].son[i];
			}
		}
	}
	int lstend[Q];
	void dfs(int x,int lste){
		lstend[x]=lste;
		if(t[x].end) lste=x;
//		printf("PING FAILTREE:%d,lste%d\n",x,lste);
		for(int v:e[x]) dfs(v,lste);
	}
	void Modify(string str){
		int cur=rt;vector<int> v;
		for(char c:str){
			cur=t[cur].son[c-'a'];
//			printf("CurPing %d\n",cur);
			int tmp=cur;
			while(!t[tmp].vis and tmp){
//				printf("Upload %d\n",tmp);
				t[tmp].include++,t[tmp].vis=true;
				v.push_back(tmp),tmp=lstend[tmp];
			}
		}
		for(int i:v) t[i].vis=false;
	}
};
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
typedef unsigned long long ull;
gp_hash_table<ull,int> cnt;
namespace Hash{
	const ull P=13331;
	int mxl;ull target[N];
	ull hash(string s){
		ull hsh=0;
		for(char c:s){
			hsh=hsh*P+ull(c);
//			cerr<<"char "<<c<<" hsh "<<hsh<<"\n";
		}
		return hsh;
	}
//	bool flg;
	void Insert(string s){
		gp_hash_table<ull,bool> vis;
		for(int i=0;i<s.size();i++){
			ull hsh=0;
			for(int j=i;j<=i+mxl-1 and j<s.size();j++){
				hsh=hsh*P+ull(s[j]);
//				if(flg) cerr<<"gog "<<j<<"\n";
				if(vis.find(hsh)!=vis.end())
					continue;
				cnt[hsh]++,vis[hsh]=true;
			}
		}
	}
};
const int B=14;
//const int B=6324;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
//	cout<<(sizeof(ACAM::t)+sizeof(SegmentTree::t));
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];
	}
	for(int i=1;i<=n;i++){
		if((int)s[i].length()>B){
			ACAM::Insert(s[i],i);
		}else{
			Hash::target[i]=Hash::hash(s[i]);
			Hash::mxl=max(Hash::mxl,(int)s[i].length());
		}
	}
//	cerr<<"MAXL "<<Hash::mxl<<"\n";
	ACAM::BuildFail(),ACAM::dfs(0,0);
	cin>>q;
	while(q--){
		int op,x;
		
		cin>>op;
//		cerr<<"go "<<q<<" op "<<op<<"\n";
		if(op==1){
			string p;cin>>p;
//			cerr<<"LINT A\n";
			ACAM::Modify(p);
//			cerr<<"LINT B\n";
//			cerr<<"SZ "<<p.size()<<"\n";
			Hash::Insert(p);
//			cerr<<"END\n";
		}else{
			cin>>x;
			if(s[x].length()>B){
				cout<<ACAM::t[ACAM::endpos[x]].include<<"\n";
			}else{
				cout<<cnt[Hash::target[x]]<<"\n";
			}
		}
	}
	return 0;
}

注：本来是想根号分治，后来发现把阈值 $B$ 设为 $0$ 可以通过。