一、基础知识：
树状结构保存字符串，查找快，判断前缀快，保存数量大。
建Trie树：
逐一把每则单词的每个字母插入Trie。插入前先看前缀是否存在。如果存在，就共享，否则创建对应的节点和边
struct Trie
{
int num;
Trie *nx[N];
};
num记录该前缀出现的次数，N是分支数，比如小写字母构成的单词的树N就是26，十进制的数字N就是10，二进制的01编码N就是2
具体建树代码：
Trie *root;
void init (Trie *t)
{
for (int j = 0; j < N; ++j) //初始化
{
t->nx[j] = NULL;
}
t->num = 0;
}
void Insert (char str[])//插入单词
{
Trie *p = root;
int len = strlen (str);
for (int i = 0; i < len; ++i)
{
int id = str[i] - 'a';
if (p->nx[id] == NULL)
{
Trie *t = new Trie;
init(t);
p->nx[id] = t;
}
p = p->nx[id];
p->num++;
}
}
查询：
查询非常简单。比如要查找的单词是int，顺着路径i -> in -> int就找到了。遇到NULL就是没有return 0;就好
int Find(char str[])//查找前缀为str的单词数
{
Trie *p = root;
int cnt,len = strlen(str);
for (int i = 0;i < len;++i)
{
int id = str[i] - 'a';
if (p->nx[id] == NULL) return 0;
p = p->nx[id];
cnt = p->num;
}
return cnt;
}
释放：
另外关于内存的释放，貌似大多数题不写释放都能A
void Delete(Trie *t)
{
for (int i = 0;i < N;++i)
{
if (t->nx[i]!=NULL) Delete(t->nx[i]);
}
delete t;
}
测试：
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 26;
struct Trie_Tree
{
struct Trie
{
int num; //前缀数
Trie *nx[N];//分支
} ;
Trie *root;
void init(Trie *t) //初始化节点
{
for (int i = 0;i < N;++i)
{
t->nx[i] = NULL;
}
t->num = 0;
}
void build()//初始化根
{
root = new Trie;
init(root);
}
void Insert(char word[]) //初始化单词
{
Trie *p = root;
int len = strlen(word);
for (int i = 0;i < len;++i)
{
int id = word[i] - 'a';//小写字母的单词就-'a'
if (p->nx[id] == NULL) //没有就新建一个
{
Trie *t = new Trie;
init(t);
p->nx[id] = t;//建
}
p = p->nx[id];//往下走
p->num++;
}
}
int Find(char word[]) //查找前缀为word的单词数
{
Trie *p = root;;
int cnt,len = strlen(word);
for (int i = 0;i < len;++i)
{
int id = word[i] - 'a';
if (p->nx[id] == NULL) return 0;//没有这样的前缀
p = p->nx[id];
cnt = p->num;//其实cnt是最后一个字母的num
}
return cnt;
}
void Delete(Trie *t)
{
for (int i = 0;i < N;++i)
{
if (t->nx[i]!=NULL) Delete(t->nx[i]);
}
delete t;
}
}text;
int main()
{
/******************************************************
测试：
1.建立一个n个单词的字典树
2.对输入的m个前缀查找在字典树中出现的次数
******************************************************/
text.build();
int n,m;cin>>n>>m;
char s[222];
for (int i = 1;i <= n;++i)
{
scanf("%s",s);
text.Insert(s);
}
for (int i = 1;i <= m;++i)
{
scanf("%s",s);
int t = text.Find(s);
if (t)
{
printf("%s shows %d times in the Trie \n",s,t);
}
else printf("%s does not exist in the Trie \n",s);
}
text.Delete(text.root);
return 0;
}
运行结果：
二、入门题目：
HDU 1251 统计难题
最基础的模板，求前缀串在Trie中出现的次数，直接建完树查询
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
using namespace std;
typedef long long ll;
#define Pintl(x) printf("%d\n",x)
const int N = 26;
struct Trie
{
int num;
Trie* nx[N];
};
Trie *root;
void init (Trie *t)
{
for (int j = 0; j < N; ++j) //初始化
{
t->nx[j] = NULL;
}
t->num = 0;
}
void Insert (char str[])//插入单词
{
Trie *p = root;
int len = strlen (str);
for (int i = 0; i < len; ++i)
{
int id = str[i] - 'a';
if (p->nx[id] == NULL)
{
Trie *t = new Trie;
init(t);
p->nx[id] = t;
}
p = p->nx[id];
p->num++;
}
}
int Find(char str[])//查找前缀为str的单词数
{
Trie *p = root;
int cnt,len = strlen(str);
for (int i = 0;i < len;++i)
{
int id = str[i] - 'a';
if (p->nx[id] == NULL) return 0;
p = p->nx[id];
cnt = p->num;
}
return cnt;
}
int main()
{
root = new Trie;
init(root);
char str[1111];
while (gets(str)&&str[0]) Insert(str);
while (gets(str)) Pintl(Find(str));
return 0;
}
HDU 1247 Hat’s Words
一个串能不能由Trie中的另外两个串合成，对每一个串枚举分界点分成两部分，在Trie中查找是否两部分都存在
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
using namespace std;
typedef long long ll;
const int N = 26;
struct Trie
{
bool isWord;
Trie *nx[N];
};
char s[50010][77];
void init(Trie *t)
{
for (int i = 0;i < N;++i)
{
t->nx[i] = NULL;
}
t->isWord = 0;
}
Trie *root;
void Insert(char word[])//插入单词
{
Trie *p = root;
int i = 0;
while (word[i]!='\0')
{
int id = word[i] - 'a';
if (p->nx[id] == NULL)
{
Trie *t = new Trie;
init(t);
p->nx[id] = t;
}
p = p->nx[id];
++i;
}
p->isWord = 1;
}
bool Find(char word[])//查找单词
{
Trie *p = root;
int i = 0;
while(word[i]!='\0')
{
int id = word[i] - 'a';
if (p->nx[id] == NULL) return 0;
p = p->nx[id];
++i;
}
return p->isWord;
}
int main()
{
// freopen("in.txt","r",stdin);
root = new Trie;
init(root);
root->isWord = 0;
int tot = 0;
while (gets(s[tot])) Insert(s[tot++]);
for (int i = 0;i < tot;++i)
{
int len = strlen(s[i]);
for (int j = 1;j < len-1;++j)
{
char t1[77] = {0};
char t2[77] = {0};
strncpy(t1,s[i],j);
strncpy(t2,s[i]+j,len-j);
if (Find(t1)&&Find(t2))
{
printf("%s\n",s[i]);
break;
}
}
}
return 0;
}
HDU 1305 Immediate Decodability
给出许多字符串，判断是否有某个串是其他串的前缀
只需判断以该串为前缀的数量即可
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
#define Sint(n) scanf("%d",&n)
#define Sll(n) scanf("%I64d",&n)
#define Schar(n) scanf("%c",&n)
#define Sint2(x,y) scanf("%d %d",&x,&y)
#define Sll2(x,y) scanf("%I64d %I64d",&x,&y)
#define Pint(x) printf("%d",x)
#define Pllc(x,c) printf("%I64d%c",x,c)
#define Pintc(x,c) printf("%d%c",x,c)
using namespace std;
typedef long long ll;
const int N = 2;
struct Trie
{
int num;
Trie *nx[N];
};
char s[22][22];
void init(Trie *t)
{
for (int i = 0;i < N;++i)//初始化
{
t->nx[i] = NULL;
}
t->num = 0;
}
Trie *root;
void Insert(char code[])//插入编码
{
Trie *p = root;
int i = 0;
while (code[i] != '\0')
{
int id = code[i] - '0';
if (p->nx[id] == NULL)
{
Trie *t = new Trie;
init(t);
p->nx[id] = t;
}
p = p->nx[id];
p->num++;
++i;
}
}
int Find(char code[]) //查找前缀为code的编码数
{
Trie *p = root;
int cnt,len = strlen(code);
for (int i = 0;i < len;++i)
{
int id = code[i] - '0';
if (p->nx[id] == NULL) return 0;
p = p->nx[id];
cnt = p->num;
}
return cnt;
}
int main()
{
int tot = 0;
root = new Trie;
init(root);
int kas = 0;
while (gets(s[++tot]))
{
// cout<<"???"<<endl;
if (s[tot][0] == '9')
{
bool is = 1;
for (int i = 1;i < tot;++i)
{
if (Find(s[i]) >= 2)
{
is = 0;
break;
}
}
if (is) printf("Set %d is immediately decodable\n",++kas);
else printf("Set %d is not immediately decodable\n",++kas);
tot = 0;
root = new Trie;
init(root);
}
else
{
Insert(s[tot]);
}
}
return 0;
}
HDU 1671 Phone List
和上面一题一样的
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
#define Sint(n) scanf("%d",&n)
#define Sll(n) scanf("%I64d",&n)
#define Schar(n) scanf("%c",&n)
#define Sint2(x,y) scanf("%d %d",&x,&y)
#define Sll2(x,y) scanf("%I64d %I64d",&x,&y)
#define Pint(x) printf("%d",x)
#define Pllc(x,c) printf("%I64d%c",x,c)
#define Pintc(x,c) printf("%d%c",x,c)
using namespace std;
typedef long long ll;
const int N = 10;//10个数字
struct Trie
{
int num;
Trie *nx[N];
} ;
char s[10007][20];
void init(Trie *t)
{
for (int i = 0;i < N;++i)//初始化
{
t->nx[i] = NULL;
}
t->num = 0;
}
Trie *root;
void Insert(char code[])//插入号码
{
Trie *p = root;
int len = strlen(code);
for (int i = 0;i < len;++i)
{
int id = code[i] - '0';
if (p->nx[id] == NULL)
{
Trie *t = new Trie;
init(t);
p->nx[id] = t;
}
p = p->nx[id];
p->num ++;
}
}
int Find(char code[]) //查找前缀为code的号码数
{
Trie *p = root;
int cnt,len = strlen(code);
for (int i = 0;i < len;++i)
{
int id = code[i] - '0';
if (p->nx[id] == NULL) return 0;
p = p->nx[id];
cnt = p->num;
}
return cnt;
}
void Delete(Trie *t)
{
for (int i = 0;i < N;++i)
{
if (t->nx[i] != NULL) Delete(t->nx[i]);
}
delete t;
}
int main()
{
int T;Sint(T);
while (T--)
{
int n;Sint(n);
root = new Trie;
init(root);
for (int i = 1;i <= n;++i)
{
scanf("%s",s[i]);
Insert(s[i]);
}
bool yes = 1;
for (int i = 1;i <= n;++i)
{
if (Find(s[i])>=2)
{
yes = 0;
break;
}
}
if (yes) puts("YES");
else puts("NO");
Delete(root);
}
return 0;
}
HDU 2846 Repository
将模式串的子串也插入树，但是为了防止一个串里的同一个字母多次算（比如add里面的d会被算2次），所以插入的时候记录下
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
#define Sint(n) scanf("%d",&n)
#define Sll(n) scanf("%I64d",&n)
#define Schar(n) scanf("%c",&n)
#define Sint2(x,y) scanf("%d %d",&x,&y)
#define Sll2(x,y) scanf("%I64d %I64d",&x,&y)
#define Pint(x) printf("%d",x)
#define Pllc(x,c) printf("%I64d%c",x,c)
#define Pintc(x,c) printf("%d%c",x,c)
using namespace std;
typedef long long ll;
const int N = 26;
struct Trie
{
int num;
int id;
Trie *nx[N];
} ;
void init(Trie *t)
{
for (int i = 0;i < N;++i)
{
t->nx[i] = NULL;
}
t->num = 0;
}
Trie *root;
void Insert(char w[],int f)
{
Trie *p = root;
int len = strlen(w);
for (int i = 0;i < len;++i)
{
int id = w[i] - 'a';
if (p->nx[id] == NULL)
{
Trie *t = new Trie;
init(t);
t->id = f;
p->nx[id] = t;
p = p->nx[id];
p->num++;
}
else
{
p = p->nx[id];
if (p->id != f)
{
p->num++;
p->id = f;
}
}
}
}
int Find(char w[])
{
Trie *p = root;
int cnt,len = strlen(w);
for (int i = 0;i < len;++i)
{
int id = w[i] - 'a';
if (p->nx[id] == NULL) return 0;
p = p->nx[id];
cnt = p->num;
}
return cnt;
}
int main()
{
int P;
while (~Sint(P))
{
root = new Trie;
init(root);
char s[22],son[22];
int id = 0;
while (P--)
{
scanf("%s",s);
int len = strlen(s);
for (int i = 0;i < len;++i)//模式串的子串也插入
{
strncpy(son,s+i,len-i);
son[len-i] = '\0';
Insert(son,id);
}
++id;
}
int Q;Sint(Q);
while (Q--)
{
char pr[22];
scanf("%s",pr);
Pintc(Find(pr),'\n');
}
}
return 0;
}
POJ 2001 Shortest Prefixes
POJ 的题目真是让人。。欲罢不能。。。。hehe~~~
每个节点初始化num为1才给过，有兴趣去Discuss里面围观下 ^_^哈哈~
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
#define Sint(n) scanf("%d",&n)
#define Sll(n) scanf("%I64d",&n)
#define Schar(n) scanf("%c",&n)
#define Sint2(x,y) scanf("%d %d",&x,&y)
#define Sll2(x,y) scanf("%I64d %I64d",&x,&y)
#define Pint(x) printf("%d",x)
#define Pllc(x,c) printf("%I64d%c",x,c)
#define Pintc(x,c) printf("%d%c",x,c)
using namespace std;
typedef long long ll;
const int N = 26;
struct Trie
{
int num;
Trie *nx[N];
};
void init(Trie *t)
{
for (int i = 0;i < N;++i)
{
t->nx[i] = NULL;
}
t->num = 1;
}
Trie *root;
void Insert(char w[])
{
Trie *p = root;
int len = strlen(w);
for (int i = 0;i < len;++i)
{
int id = w[i] - 'a';
if (p->nx[id] == NULL)
{
Trie *t = new Trie;
init(t);
p->nx[id] = t;
}
else p->nx[id]->num++;
p = p->nx[id];
}
}
int Search(char w[])
{
Trie *p = root;
int len = strlen(w);
for (int i = 0;i < len;++i)
{
int id = w[i] - 'a';
// if (p->nx[id] == NULL) return 0;//应该没有NULL
p = p->nx[id];
if (p->num <= 1) return i;
}
return len-1;
}
char s[11111][33];
int main()
{
// freopen("in.txt","r",stdin);
int tot = 0;
root = new Trie;
init(root);
while (~scanf("%s",s[++tot]))
{
Insert(s[tot]);
}
for (int i = 1;i <= tot;++i)
{
printf("%s ",s[i]);
int ln = Search(s[i]);
for (int j = 0;j <= ln;++j) putchar(s[i][j]);
puts("");
}
return 0;
}
HDU 5687 Problem C
完全就是字典树的操作，添加了一个delete操作，反正内存不要钱 瞎写~~~
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
#define Sint(n) scanf("%d",&n)
#define Sll(n) scanf("%I64d",&n)
#define Schar(n) scanf("%c",&n)
#define Sint2(x,y) scanf("%d %d",&x,&y)
#define Sll2(x,y) scanf("%I64d %I64d",&x,&y)
#define Pint(x) printf("%d",x)
#define Pllc(x,c) printf("%I64d%c",x,c)
#define Pintc(x,c) printf("%d%c",x,c)
using namespace std;
typedef long long ll;
const int N = 26;
struct Trie
{
int num;
Trie *nx[N];
};
void init(Trie *t)
{
for (int i = 0;i < N;++i)
{
t->nx[i] = NULL;
}
t->num = 0;
}
Trie *root;
void Insert(char w[])
{
Trie *p = root;
int len = strlen(w);
for (int i = 0;i < len;++i)
{
int id = w[i] - 'a';
if (p->nx[id] == NULL)
{
Trie *t = new Trie;
init(t);
p->nx[id] = t;
}
p = p->nx[id];
p->num++;
}
}
int Find(char w[])
{
Trie *p = root;
int len = strlen(w);
for (int i = 0;i < len;++i)
{
int id = w[i] - 'a';
if (p->nx[id] == NULL) return 0;
p = p->nx[id];
}
return p->num;
}
void Delete(char w[],int num)
{
Trie *p = root;
int len = strlen(w);
for (int i = 0;i < len;++i)
{
int id = w[i] - 'a';
if (p->nx[id] == NULL) return;
p->num -= num;//delete
p = p->nx[id];
}
p->num = 0;
for (int i = 0;i < N;++i) p->nx[i] = NULL;
}
int main()
{
char op[110],word[330];
int T;
while (Sint(T) == 1)
{
root = new Trie;
init(root);
while (T--)
{
scanf("%s %s",op,word);
if (!strcmp(op,"insert"))
{
Insert(word);
}
else if (!strcmp(op,"search"))
{
if (Find(word)) puts("Yes");
else puts("No");
// Pintc(Find(word),'\n');
}
else if (!strcmp(op,"delete"))
{
int num = Find(word);
if (num) Delete(word,num);
}
}
}
return 0;
}
POJ 2503 Babelfish
映射的话第一眼想到的用map 不过为了练习Trie还是写了字典树版本的
这里需要将所有的左边的单词都保存下来，然后Trie树保存的是该单词对应的翻译的编号
map版和Trie版的AC代码都贴上，用map的话，代码短但是时间长了4倍
map版：
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
#define Sint(n) scanf("%d",&n)
#define Sll(n) scanf("%I64d",&n)
#define Schar(n) scanf("%c",&n)
#define Sint2(x,y) scanf("%d %d",&x,&y)
#define Sll2(x,y) scanf("%I64d %I64d",&x,&y)
#define Pint(x) printf("%d",x)
#define Pllc(x,c) printf("%I64d%c",x,c)
#define Pintc(x,c) printf("%d%c",x,c)
using namespace std;
typedef long long ll;
map<string,string>mp;
char s1[22],s2[22];
char s[33];
int main()
{
while (gets(s))
{
if (s[0] == '\0') break;
sscanf(s,"%s %s",s1,s2);
mp[s2] = s1;
}
while (~scanf("%s",s))
{
if (mp[s].size()) cout<<mp[s]<<endl;
else puts("eh");
}
return 0;
}
Trie版：
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
#define Sint(n) scanf("%d",&n)
#define Sll(n) scanf("%I64d",&n)
#define Schar(n) scanf("%c",&n)
#define Sint2(x,y) scanf("%d %d",&x,&y)
#define Sll2(x,y) scanf("%I64d %I64d",&x,&y)
#define Pint(x) printf("%d",x)
#define Pllc(x,c) printf("%I64d%c",x,c)
#define Pintc(x,c) printf("%d%c",x,c)
using namespace std;
typedef long long ll;
const int N = 26;
struct Trie
{
int id;//标记该串 是和第几个单词对应 没有对应就是-1
Trie *nx[N];
};
char s1[100005][14],s2[100005][14];
void init(Trie *t)
{
for (int i = 0;i < N;++i)
{
t->nx[i] = NULL;
}
t->id = -1;
}
Trie *root;
void Insert(char w[],int ID)
{
Trie *p = root;
int len = strlen(w);
for (int i = 0;i < len;++i)
{
int id = w[i] - 'a';
if (p->nx[id] == NULL)
{
Trie *t = new Trie;
init(t);
p->nx[id] = t;
}
p = p->nx[id];
}
p->id = ID;
}
int Find(char w[])//查找单词是否有对应的编号
{
Trie *p = root;
int len = strlen(w);
for (int i = 0;i < len;++i)
{
int id = w[i] - 'a';
if (p->nx[id] == NULL) return -1;
p = p->nx[id];
}
return p->id;
}
int main()
{
int ID = 0;
root = new Trie;
init(root);char s[33];
while (gets(s))
{
if (s[0] == '\0') break;
sscanf(s,"%s %s",s1[ID],s2[ID]);
Insert(s2[ID],ID);
++ID;
}
while (~scanf("%s",s))
{
int id = Find(s);
if (id == -1) puts("eh");
else printf("%s\n",s1[id]);
}
return 0;
}
HDU 1075 What Are You Talking About
和上面一题一样，不过多了标点符号的处理
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
#define Sint(n) scanf("%d",&n)
#define Sll(n) scanf("%I64d",&n)
#define Schar(n) scanf("%c",&n)
#define Sint2(x,y) scanf("%d %d",&x,&y)
#define Sll2(x,y) scanf("%I64d %I64d",&x,&y)
#define Pint(x) printf("%d",x)
#define Pllc(x,c) printf("%I64d%c",x,c)
#define Pintc(x,c) printf("%d%c",x,c)
using namespace std;
typedef long long ll;
const int N = 26;
struct Trie
{
int id;//标记翻译的英文串的编号
Trie *nx[N];
};
char s1[1000007][22] ,s2[1000007][22];
void init(Trie *t)
{
for (int i = 0;i < N;++i)
{
t->nx[i] = NULL;
}
t->id = -1;
}
Trie *root;
void Insert(char w[],int ID)
{
Trie *p = root;
int len = strlen(w);
for (int i = 0;i < len;++i)
{
int id = w[i] - 'a';
if (p->nx[id] == NULL)
{
Trie *t = new Trie;
init(t);
p->nx[id] = t;
}
p = p->nx[id];
}
p->id = ID;
}
int Find(char w[])//查找火星文对应的英文的编号，没有返回-1
{
Trie *p = root;
int len = strlen(w);
for (int i = 0;i < len;++i)
{
int id = w[i] - 'a';
if (p->nx[id] == NULL) return -1;
p = p->nx[id];
}
return p->id;
}
char s[3333];
int main()
{
int ID = 0;
root = new Trie;init(root);
scanf("%s",s);//START
getchar();
while (gets(s))
{
if (strcmp(s,"END") == 0) break;
sscanf(s,"%s %s",s1[ID],s2[ID]);
Insert(s2[ID],ID);
++ID;
}
scanf("%s",s);//START
getchar();
while (gets(s))
{
if (strcmp(s,"END") == 0) break;
int k = 0;
char w[33];//保存单词
for (int i = 0;s[i];++i)//处理标点符号
{
if (islower(s[i])) w[k++] = s[i];
else //s[i]是标点
{
w[k] = '\0';
int id = Find(w);
if (id == -1) printf("%s",w);
else printf("%s",s1[id]);
putchar(s[i]);//标点输出
k = 0; //初始化
mem(w,0);
}
}
puts("");
}
return 0;
}
三、总结：
字典树算入门了，其实很多时候不用字典树用map啊，快排啊，等等一些乱七八糟的算法也可以解字典树的题，
不过一般来说字典树都会更快一些，map用着多爽啊，不过如果哪天遇到恶意出题人卡map， hehe~~~
不会的还很多，路漫漫而修远兮，吾将上下而求索
