死亡回放:只有WA和AC
之前我使用了指针导致MLE,这次我学着开了个超大数组,但是还是没过 P8306指针方法
code:
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int S=62;//A、a、0:26+26+10
const int N=3000005;
pair<int,int> trie[N][S];
int allpoint=0;
int getsize_t(char ch){
if(ch>='0'&&ch<='9')return ch-'0'+52;
else if(ch>='a'&&ch>='z')return ch-'a'+26;
else return ch-'A';
}
void empty(int x){
for(int i=0;i<S;i++){
trie[x][i].first=0;
trie[x][i].second=-1;
}
}
void insert(string word){
int pointer=0,tmpw;
for(int i=0;i<word.size();i++){
tmpw=getsize_t(word[i]);
if(trie[pointer][tmpw].first==0){
allpoint++;
empty(allpoint);
trie[pointer][tmpw].second=allpoint;
}
trie[pointer][tmpw].first++;
pointer=trie[pointer][tmpw].second;
}
}
int find(string word){
int pointer=0,tmpw;
int now;
for(int i=0;i<word.size();i++){
tmpw=getsize_t(word[i]);
if(trie[pointer][tmpw].second==-1||trie[pointer][tmpw].first==0)return 0;
now=trie[pointer][tmpw].first;
pointer=trie[pointer][tmpw].second;
}
return now;
}
void start(){
allpoint=0;empty(0);
int n,q;cin>>n>>q;
string s,t;
for(int i=0;i<n;i++){cin>>s;insert(s);}
for(int i=0;i<q;i++){cin>>t;cout<<find(t)<<endl;}
}
int main(){
int tq;cin>>tq;
for(int i=0;i<tq;i++)start();
return 0;
}