P8306字典树

#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#define endl '\n'
using namespace std;
const int N = 3e6 + 10;
int cnt[N], son[N][64], idx;
void insert(string& s) {
	int p = 0;
	for (int i = 0; i < s.size(); ++i) {
		   int u;
		   if (isupper(s[i]))u = s[i] - 'A' + 36;
		   else if (islower(s[i])) u = s[i] - 'a' + 10;
		   else u = s[i] - '0';
		   if (!son[p][u]) son[p][u] = ++idx;
		   p = son[p][u];
		   cnt[p]++;
	}
}
void search(string& s) {
	  int p = 0;
	  for (int i = 0; i < s.size(); ++i) {
		    int u;
			if (isupper(s[i]))u = s[i] - 'A' + 36;
			else if (islower(s[i]))u = s[i] - 'a' + 10;
			else u = s[i] - '0';
			if (!son[p][u]) { cout << 0 << endl; return; }
			p = son[p][u];
	  }
	  cout << cnt[p] << endl;
}
void solve() {
	  string s;
	  int n, q; cin >> n >> q;
	  for (int i = 0; i < n; ++i) {
		   cin >> s;
		   insert(s);
	  }
	  for (int i = 0; i < q; ++i) {
		  cin >> s;
		 search(s);
	  }
	  for (int i = 0; i <= idx; ++i)
		  for (int j = 0; j <= 63; ++j)
			  son[i][j] = 0;
	  for (int i = 0; i <= idx; ++i)cnt[i] = 0;
	  idx = 0;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int t; cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

memset和for循环的耗时是真差不太多,我还一直一直以为memset是针对内存的,合计就是个包装完的for,而且除了0,-1,赋不了其他值,选择性的使用,除非非常确定,不然就选择for