RT,救救孩子吧

思路和第二篇题解一样，对着COCI的标程写的。

这是我的代码：

#include <bits/stdc++.h>
using namespace std;
int n,q,son[1500005][35],cnt,cmt,st[3000005],ed[3000005],ccnt,an[3000005];
char str[3000005];
struct _hash{
	int base=3137,mod=1e9+7;
	int base2=53,mod2=1610612741;
	int h=0,h2=0;
	bool operator<(_hash b)const{
		if(h!=b.h)return h<b.h;
		return h2<b.h2;
	}
	void add_char (char c) {
	    h=(h*1ll*base+c-'a'+1)%mod;
	    h2=(h2*1ll*base2+c-'a'+1)%mod2;
	}
};
_hash ha[3000005];
string pref[100005],suff[100005];
vector<vector<_hash> > hashes;
vector<_hash> emp;
set<_hash> S;
map<_hash,vector<int> > mp;
void init(char* str){
	int len=strlen(str);
	ha[0]=_hash();
	reverse(str,str+len);
	for(int i=0;i<len;i++){
		ha[i+1]=ha[i];
		ha[i+1].add_char(str[i]);
	}
	reverse(ha,ha+len+1);
}
void add(int loc,char* str){
	int len=strlen(str),u=0;
	an[0]++,hashes[0].push_back(ha[0]);
	for(int i=0;i<len;i++){
		int c=str[i]-'a';
		if(!son[u][c]){
			son[u][c]=++cnt;
			hashes.push_back(emp);
		}
		u=son[u][c];
		an[u]++;
		hashes[u].push_back(ha[i+1]);
	}
}
void dfs(int u){
	st[u]=++ccnt;
	int sz=hashes[u].size();
	for(int i=0;i<sz;i++){
		if(S.count(hashes[u][i])){
			mp[hashes[u][i]].push_back(st[u]);
		}
	}
	for(int i=0;i<26;i++){
		if(son[u][i])dfs(son[u][i]);
	}
	ed[u]=++ccnt;
}
int query(string str,_hash h){
	int len=str.size(),u=0;
	for(int i=0;i<len;i++){
		if(!son[u][str[i]-'a'])return 0;
		u=son[u][str[i]-'a'];
	}
	return upper_bound(mp[h].begin(),mp[h].end(),ed[u])-lower_bound(mp[h].begin(),mp[h].end(),st[u]);
}
signed main(){
	cin>>n>>q;
	hashes.push_back(emp);
	for(int i=1;i<=n;i++){
		cin>>str;
		init(str);
		add(i,str);
	}
	for(int i=1;i<=q;i++){
		string stt;
		cin>>stt;
		pref[i]=stt.substr(0,stt.find("*"));
		suff[i]=stt.substr(stt.find("*")+1);
		_hash h;
		for(int j=suff[i].size()-1;j>=0;j--)
			h.add_char(suff[i][j]);
		S.insert(h);
	}
	dfs(0);
	for(int i=1;i<=q;i++){
		_hash h;
		for(int j=suff[i].size()-1;j>=0;j--)
			h.add_char(suff[i][j]);
		cout<<query(pref[i],h)<<endl;
	}
	return 0;
}

再附上COCI的标程