先对输入的模式串进行处理建树
void insert(string x) { int p=0;//创建根节点 for(int i=0;i<x.size();i++) { int y=x[i]-'0';//对字符进行处理 trie[p][y]=++id; p=trie[p][y];//进入下一层 red[p]++;//储存到该点有多少模板串有此作为前缀 } }
之后对每次询问进行查询
int find(string x) { int p=0; for(int i=0;i<x.size();i++) { int y=x[i]-'0';//处理模板串 if(!trie[p][y])//未开创此条路线，直接结束 return 0; p=trie[p][y];//进入下一层 } return red[p];//返回答案 }
因为是多实例，每次对数组进行手动清空处理（用memset会MLE）
for(int i=0;i<=id;i++) { for(int j=0;j<100;j++) trie[i][j]=0; } for(int i=0;i<=id;i++) red[i]=0; id=0;
AC代码：
#include<bits/stdc++.h> using namespace std; int trie[3000009][100]; int red[3000009]; int id; void insert(string x) { int p=0; for(int i=0;i<x.size();i++) { int y=x[i]-'0'; trie[p][y]=++id; p=trie[p][y]; red[p]++; } } int find(string x) { int p=0; for(int i=0;i<x.size();i++) { int y=x[i]-'0'; if(!trie[p][y]) return 0; p=trie[p][y]; } return red[p]; } int main() { int t; cin>>t; while(t--) { int n,q; cin>>n>>q; for(int i=0;i<=id;i++) { for(int j=0;j<100;j++) trie[i][j]=0; } for(int i=0;i<=id;i++) red[i]=0; id=0; for(int i=0;i<n;i++) { string x; cin>>x; insert(x); } for(int i=0;i<q;i++) { string x; cin>>x; cout<<find(x)<<endl; } } return 0; }
