我怀疑本题并不能体现字典树的最明显特征

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

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

尽管我退役了，但是我还是花了 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 的字符串有几个”），否则不管怎么加强，感觉哈希橄榄都是防不住的。