过了中间四个点。

思路：

对于每个前缀，用哈希存一遍。可以发现总共最多只会存 $3\times10^6$ 遍。且每次插入必定是 $O(1)$ 的。（因为我是在插入的同时计算当前的哈希值，所以复杂度就算进插入里了）

储存我是用双哈希，因为直接比较字符串的复杂度开销很大。查询的期望时间复杂度是 $O(\frac{n}{m} \log \frac{n}{m})$（使用了 set 去重），其中我设 $m=10^6+7$。

清空我只清空用过的，顶多就只会清空 $\sum\lvert S_i\rvert$ 个 list 中的顶多 $\sum\lvert S_i\rvert$ 个元素，应该不会有什么问题吧。

总的时间复杂度应该是 $O(\sum\lvert S_i\rvert +\frac{n}{m} \log \frac{n}{m})$。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD(1e6+7);
const int BASE1(131);
const int BASE2(13331);

int t, n, q, ha1, base1;
unsigned int ha2, base2;
string str, tmp;
list<pair<unsigned int, int>> li[MOD];
vector<int> vec;

void clear(){
	for (int i: vec) li[i].clear();
	vec.clear();
}

void insert(string str, int ha1, int ha2, int ind){
	vec.push_back(ha1);
	li[ha1].push_back({ha2, ind});
}

int query(string str){
	set<int> st;
	
	ha1 = ha2 = 0;
    base1 = base2 = 1;
    for (char i: str){
    	ha1 = (ha1 + i * base1) % MOD;
		base1 = (base1 * BASE1) % MOD;
		ha2 += i * base2;
		base2 *= BASE2;
	}
	
	for (auto i: li[ha1]){
		if (i.first == ha2) st.insert(i.second);
	}
	return st.size();
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> t;
    while (t--){
    	cin >> n >> q;
    	clear();
    	for (int i(1); i<=n; ++i){
    		cin >> str;
    		tmp = "";
    		
    		ha1 = ha2 = 0;
    		base1 = base2 = 1;
    		for (char j: str){
    			ha1 = (ha1 + j * base1) % MOD;
    			base1 = (base1 * BASE1) % MOD;
    			ha2 += j * base2;
    			base2 *= BASE2;
    			
    			tmp += j;
    			insert(tmp, ha1, ha2, i);
			}
		}
		while (q--){
			cin >> str;
			cout << query(str) << '\n';
		}
	}

    return 0;
}