如题，首先我们发现，字符串哈希板板 也是某种匹配。

因此我们非常合理地认为，只要我们把读入字符串的所有前缀全部丢到哈希表里面，这题就做完了。

尽管我退役了，但是我还是花了 10 分钟写了下面这个玩意：

#include<bits/stdc++.h>
using namespace std;
#define u128 unsigned long long
unordered_map<u128,int> tr;
int T,n,q;
u128 v[3000005];
char s[3000005];
int main()
{
	v[0]=1;
	for(int i=1;i<=3000000;i++)
		v[i]=v[i-1]*131;
	for(scanf("%d",&T);T;T--)
	{
		scanf("%d%d",&n,&q);
		tr.clear();
		for(int i=1;i<=n;i++)
		{
			scanf("%s",s);
			u128 tot=0;
			for(int j=0;s[j];j++)
			{
				tot+=s[j]*v[j];
				if(tr.count(tot))tr[tot]++;
				else tr[tot]=1;
			}
		}
		for(;q;q--)
		{
			scanf("%s",&s);
			u128 tot=0;
			for(int j=0;s[j];j++)
				tot+=s[j]*v[j];
			if(tr.count(tot))printf("%d\n",tr[tot]);
			else puts("0");
		}
	}
	return 0;
}

一举 AC 本题。

我觉得，考察字典树的话，应该还是要加入偏序关系（例如“字典序不大于 $s$ 的字符串有几个”），否则不管怎么加强，感觉哈希橄榄都是防不住的。