题解 | 记票统计 trie树

#include<iostream>//因为好久没复习这个知识点所以强行用一下
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
#define int long long 
const int N=150;//一开始开的15，不知道怎么开小了，数组越界，只好改大点了
vector<string> Q;//记录所有字符串，方便最后打印输出
bool r[110];//开一个数组记录一下该下标处的位置是否是个人名的结尾
int tree[N][26],idx,iex;//标准trie树
int cnt[110];//记录票数
int n,m;
void creat(string s)//创建树
{
int p=0;
for(int i=0;i<s.size();i++)
{int u=s[i]-'A';
if(!tree[p][u])tree[p][u]=++idx;//没开节点就开个
p=tree[p][u];//延伸节点
}
r[p]=true;


}
bool add_c(string s)//投票，同创建
{int p=0;
for(int i=0;i<s.size();i++)
{int u=s[i]-'A';
if(!tree[p][u])return 0;//找不到
p=tree[p][u];
}
if(r[p]){cnt[p]++;return 1;}//判断是否为有效票，如果以该字母结尾的下标是个名字（也就是true）则有效
return 0;//找到了，但不以它结尾


}
void print(string &s)//打印
{int p=0;
for(int i=0;i<s.size();i++)
{int u=s[i]-'A';p=tree[p][u];

}cout<<s<<' '<<':'<<' '<<cnt[p]<<endl;

}
signed main()
{cin>>n;
for(int i=0;i<n;i++)
{string s;
cin>>s;Q.push_back(s);
creat(s);


}cin>>m;int IN=0;
for(int i=0;i<m;i++)
{string s;
cin>>s;
bool flag=add_c(s);
if(!flag)IN++;

}
for(int i=0;i<Q.size();i++)
{print(Q[i]);

}cout<<"Invalid : "<<IN<<endl;

return 0;

}