字典树(trie)：或名前缀树，哈希树的变种，大多题目（非水题）与哈希树套用求解。矮+胖为其显著特征，以空间换时间的典例。
通过利用字符串的公共前缀可实现字符串的快速查询。
板子如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e6+5;
int tot=0;
int tree[maxn][30];
int flag[maxn];
void add(char *s)
{
int len=strlen(s);
int root=0;
for(int i=0;i<len;i++)
{
int id=s[i]-'a';
if(!tree[root][id]) tree[root][id]=++tot;
root=tree[root][id];
}
flag[root]=1;
}
bool fid(char *s)
{
int len=strlen(s);
int root=0;
for(int i=0;s[i];i++)
{
int id=s[i]-'a';
if(tree[root][id]==0)
{
return 0;
}
root=tree[root][id];
}
return flag[root];
}
/*
删除操作：
三种可能：
1、没找到该单词
2、找到叶节点时、叶节点的cnt标志清零，代表该节点不是叶节点
3、当前节点没有其他的孩子节点时，可直接删除该节点
*/
void del(char *str,int word)
{
int len=strlen(str);
int root=0;
if(word==0)//未找到
{
return ;
}
for(int i=0;i<len;i++)
{
int id=str[i]-'a';
if(tree[root][id]==0)//没有子节点
return;
sum[root]-=cnt;
root=tree[root][id];
}
sum[root]=0;
for(int i=0;i<26;i++)
{
tree[root][id]=0;
}
}
struct Node{
int sum;//前缀
int next[26];//子节点
void init(){
sum=0;
memset(next,-1,sizeof next);
}
}tire[N];
int tot;
void add(char *str){
int len=strlen(str);
int root=0;
for(int i=0;i<len;i++){
int x=str[i]-'a';
if(tire[root].next[x]==-1)
tire[root].next[x]=tot++;
root=tire[root].next[x];
tire[root].sum++;
}
}
int fid(char *str){
int len=strlen(str);
int root=0;
for(int i=0;i<len;i++){
int x=str[i]-'a';
if(tire[root].next[x]==-1)
return 0;
root=tire[root].next[x];
}
return tire[root].sum;
}
void del(char *str,int word){
int len=strlen(str);
int root=0;
if(word<0)
return;
for(int i=0;i<len;i++){
int x=str[i]-'a';
if(tire[root].next[x]==-1)
return;
tire[root].sum-=word;
root=tire[root].next[x];
}
tire[root].sum=0;
for(int i=0;i<26;i++)
tire[root].next[i]=-1;
}
int main(){
tot=1;
for(int i=0;i<N;i++)
tire[i].init();
int t;
scanf("%d",&t);
while(t--){
char str[10],word[35];
scanf("%s%s",str,word);
if(str[0]=='i')//插入
add(word);
else if(str[0]=='d')//删除
del(word,fid(word));
else{//查询
if(fid(word)>0)
printf("Yes\n");
else
printf("No\n");
}
}
return 0;
}
//前缀出现次数
int trie[400001][26],tot;
int sum[400001];
void add(char *s){
int root=0;
int len=strlen(s);
for(int i=0;i<len;i++){
int id=s[i]-'a';
if(!trie[root][id])
trie[root][id]=++tot;
sum[trie[root][id]]++;//前缀保存
root=trie[root][id];
}
}
int fid(char *s){
int root=0;
int len=strlen(s);
for(int i=0;i<len;i++){//root经过循环后变成前缀最后一个字母所在位置
int id=s[i]-'a';
if(!trie[root][id])
return 0;
root=trie[root][id];
}
return sum[root];
}
int main(){
int n,m;
char s[11];
scanf("%d",&n);//插入单词个数
for(int i=1;i<=n;i++){
scanf("%s",s);
add(s);
}
scanf("%d",&m);//查询次数
for(int i=1;i<=m;i++){
scanf("%s",s);
printf("%d\n",add(s));
}
}
//单词|前缀是否出现
int tot=1;
int trie[N][26];//trie[rt][x]=tot,root是上个节点编号，x是字母，tot是下个节点编号
//bool vis[N];//查询整个单词用
void add(char *s,int root){
for(int i=0;s[i];i++){
int x=s[i]-'a';
if(trie[root][x]==0)//现在插入的字母在之前同一节点处未出现过
trie[root][x]=++tot;//字母插入一个新的位置，否则不做处理
root=trie[root][x];//为下个字母的插入做准备
}
//vis[root]=true;//标志该单词末位字母的尾结点，在查询整个单词时用
}
bool add(char *s,int root){
for(int i=0;s[i];i++){
int x=s[i]-'a';
if(trie[rt][x]==0)
return false;//以rt为头结点的x字母不存在，返回0
rt=trie[rt][x];//为查询下个字母做准备
}
return true;
//return vis[rt];//查询整个单词时
}
int main(){
int n,m;
char s[22];
tot=0;
scanf("%d",&n);//插入单词个数
for(int i=1;i<=n;i++){
scanf("%s",s);
add(s,1);
}
scanf("%d",&m);//查询单词个数
for(int i=1;i<=n;i++){
scanf("%s",s);
if(fid(s,1))
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
例题：
A：
板子题：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
const int maxn=2e6+5;
int tree[maxn][30],tot=0;//26¸ö×Öĸ
bool flag[maxn];
int sum[100007];
char a[100007];
typedef long long ll;
void add(char *s)
{
int root=0,id,len=strlen(s);
for(int i=0;i<len;++i)
{
id=s[i]-'a';
if(!tree[root][id]) tree[root][id]=++tot;
sum[tree[root][id]]++;
root=tree[root][id];
}
//flag[root]=true;
}
ll fid(char *s)
{
//long long res=0;
int root=0,id,len=strlen(s);
for(int i=0;i<len;++i)
{
id=s[i]-'a';
if(!tree[root][id]) return 0;
root=tree[root][id];
}
return sum[root];
//if(flag[root]) return 1;
/*else
return 0;*/
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
scanf("%s",a);
add(a);
}
int m;
scanf("%d",&m);
while(m--)
{
scanf("%s",a);
printf("%lld\n",fid(a));
}
return 0;
}
B：
思路：有趣题，可通过建双trie储存字符串拼接对比得到结果。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<cmath>
#include<sstream>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int maxn=2e6+5;
int tree1[maxn][30],tree2[maxn][30];
bool flag1[maxn],flag2[maxn];
int vis[maxn];
int tot1=0,tot2=0;
void add1(char *s){
int root=0,id,len=strlen(s);
for(int i=0;i<len;++i){
id=s[i]-'a';
if(!tree1[root][id]) tree1[root][id]=++tot1;
root=tree1[root][id];
}
flag1[root]=true;
}
void add2(char *s){
int root=0,id,len=strlen(s);
for(int i=0;i<len;++i){
id=s[i]-'a';
if(!tree2[root][id]) tree2[root][id]=++tot2;
root=tree2[root][id];
}
flag2[root]=true;
}
void find1(char *s){
int root=0,id,len=strlen(s);
for(int i=0;i<len;++i){
id=s[i]-'a';
root=tree1[root][id];
if(flag1[root]) vis[i]++;
}
}
void find2(char *s){
int root=0,id,len=strlen(s);
for(int i=0;i<len;++i){
id=s[i]-'a';
root=tree2[root][id];
if(flag2[root]) vis[len-i-2]++;
}
}
char a[50005][100];
set<string> ans;
int main(){
int cnt=0;
while(scanf("%s",a[cnt++])!=EOF){
add1(a[cnt-1]);
strrev(a[cnt-1]);
add2(a[cnt-1]);
strrev(a[cnt-1]);
}
for(int i=0;i<cnt;++i){
int len=strlen(a[i]);
for(int j=0;j<len;++j) vis[j]=0;
find1(a[i]);
strrev(a[i]);
find2(a[i]);
strrev(a[i]);
for(int j=0;j<len;++j){
if(vis[j]>=2){
string tp=a[i];
ans.insert(tp);
break;
}
}
}
for(auto it=ans.begin();it!=ans.end();++it){
cout<<*it<<endl;
}
return 0;
}
C:HDU-1251
思路：和A类似，板子题
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e6+5;
int tree[maxn][30],tot=0;//26¸ö×Öĸ
bool flag[maxn];
int sum[100007];
char a[100007];
typedef long long ll;
void add(char *s)
{
int root=0,id,len=strlen(s);
for(int i=0;i<len;++i)
{
id=s[i]-'a';
if(!tree[root][id]) tree[root][id]=++tot;
sum[tree[root][id]]++;
root=tree[root][id];
}
//flag[root]=true;
}
ll fid(char *s)
{
//long long res=0;
int root=0,id,len=strlen(s);
for(int i=0;i<len;++i)
{
id=s[i]-'a';
if(!tree[root][id]) return 0;
root=tree[root][id];
}
return sum[root];
//if(flag[root]) return 1;
/*else
return 0;*/
}
int main()
{
while(gets(a))
{
if(a[0]=='\0') break;
add(a);
}
char b[maxn];
while(scanf("%s",b)!=EOF)
{
printf("%lld\n",fid(b));
}
return 0;
}
D：Immediate Decodability HDU-1305
思路：字典树的第二姿势，即对前缀的查询，稍微改改板子。若有字符串作为其他字符串的前缀，即为可消除的，也就是有一个串上非末尾阶段有flag标记。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<cmath>
#include<sstream>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int maxn=2e6+5;
int tree[maxn][15],sum[maxn],tot=0;
char a[10005][15];
int T,n;
void add(char *s) {
int root=0,id,len=strlen(s);
for(int i=0; i<len; ++i) {
id=s[i]-'0';
if(!tree[root][id]) tree[root][id]=++tot;
root=tree[root][id];
sum[root]++;
}
}
bool fid(char *s) {
int root=0,id,len=strlen(s),tp=0;
for(int i=0; i<len; ++i) {
id=s[i]-'0';
root=tree[root][id];
if(sum[root]>=2) tp++;
}
if(tp==len) return false;
else return true;
}
int main()
{
int k=1;
int cnt=0;
while(scanf("%s",a[cnt])!=EOF){
if(a[cnt][0]!='9'){
add(a[cnt]);
cnt++;
}
else{
bool pd=0;
for(int i=0;i<cnt;i++){
if(!fid(a[i])){
pd=1;
break;
}
}
if(!pd) printf("Set %d is immediately decodable\n",k++);
else printf("Set %d is not immediately decodable\n",k++);
cnt=0;
for(int i=0;i<=tot;++i){
for(int j=0;j<10;++j){
tree[i][j]=0;
}
}
}
}
return 0;
}
E ： What Are You Talking About HDU - 1075
用map做的，这里就不开了，到时候开map的时候会拿出来写的。
F：Phone List poj-3630
在poj上6w多KB过的，学长搬过来卡内存，就不会了。
也就gg了17发而已。
G： Shortest Prefixes POJ - 2001
思路：每个每个去找最大的没有flag的地方。
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
const int maxn=2e6+5;
int tree[maxn][30],tot=0;//26¸ö×Öĸ
bool flag[maxn];
int sum[100007];
typedef long long ll;
void add(char *s)
{
int root=0,id,len=strlen(s);
for(int i=0; i<len; ++i)
{
id=s[i]-'a';
if(!tree[root][id]) tree[root][id]=++tot;
root=tree[root][id];
sum[root]++;
}
flag[root]=1;
}
string fid(char *s)
{
string ans=""; //long long res=0;
int root=0,id,len=strlen(s);
for(int i=0; i<len; ++i)
{
id=s[i]-'a';
root=tree[root][id];
ans+=s[i];
if(sum[root]==1) return ans;
}
return ans;
}
char a[1007][30];
int main()
{
int j=0;
int cot=0;
while(scanf("%s",a[j++])!=EOF)
{
//if(cot==12) break;
add(a[j-1]);
//cot++;
//printf("1\n");
}
//printf("J:%d\n",j);
for(int i=0; i<j; ++i)
{
//cout<<"1"<<endl;
cout<<a[i]<<" "<<fid(a[i])<<endl;
}
return 0;
}
H - 全文检索 HDU - 1277
瞎搞过的，极其难看，这里就不提了。
还有几个快乐的题比如说poj的1816，很有意思。
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int maxn=2e6+5;
int tree[maxn][30],tot=0;
bool flag[maxn],vis[maxn];
int n,m,p[maxn];
int add(char *s) {
int root=0,id,len=strlen(s);
for(int i=0; i<len; ++i) {
if(s[i]=='*') id=26;
else if(s[i]=='?') id=27;
else id=s[i]-'a';
if(!tree[root][id]) tree[root][id]=++tot;
root=tree[root][id];
}
flag[root]=1;
return root;
}
void fid(char *s,int nroot,int pos) {
int root=nroot,id,len=strlen(s);
if(pos>len) return;
if(pos==len && flag[root]) {
vis[root]=1;
}
if(tree[root][26]) { //*
for(int j=pos; j<=len; ++j) {
fid(s,tree[root][26],j);
}
}
if(tree[root][27]) { //£¿
fid(s,tree[root][27],pos+1);
}
id=s[pos]-'a';
if(s[pos]>='a'&&s[pos]<='z'&&tree[root][id]) {
fid(s,tree[root][id],pos+1);
}
}
char tp[100];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i)
{
scanf("%s",tp);
p[i]=add(tp);
}
while(m--!=0)
{
scanf("%s",tp);
fid(tp,0,0);
int ok=0;
for(int i=0;i<n;++i)
{
if(vis[p[i]])
{
printf("%d ",i);
ok=1;
}
}
if(!ok) printf("Not match\n");
else
printf("\n");
for(int i=0;i<n;++i) vis[p[i]]=0;
}
return 0;
}
搞懂哈希之后会继续补的。
京公网安备 11010502036488号