作用
看以下几个题：
1、 给出n个单词和m个询问，每次询问一个单词，回答这个单词是否在单词表中出现过。
答：简单！map，短小精悍。
2、给出n个单词和m个询问，每次询问一个前缀，回答询问是多少个单词的前缀。
答：map，把每个单词拆开。
judge：n<=200000，TLE！
这就需要一种高级数据结构——Trie树（字典树）
概念
单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。
优点：
利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。
Trie的数据结构定义：
以小写字母字典树为例
#define MAX 26 //根据需要变化};
typedef struct Trie {
Trie *next[MAX];
int count;
next 表示每层有多少种类的数，也就是子树的个数。例子是小写字母，为26。
count 表示一个字典树到此有多少相同前缀的数目。
操作
生成字典树：
思路：
从左到右扫这个单词，如果字母在相应根节点下没有出现过，就插入这个字母；否则沿着字典树往下走，看单词的下一个字母。
代码：
void createTrie(char *str)
{
int len = strlen(str);
Trie *p = root, *q;
for(int i=0; i<len; ++i)
{
int id = str[i]-'0';
if(p->next[id] == NULL)
{
q = (Trie *)malloc(sizeof(Trie));
q->v = 1; //初始v==1
for(int j=0; j<MAX; ++j)
q->next[j] = NULL;
p->next[id] = q;
p = p->next[id];
}
else
{
p->next[id]->v++;
p = p->next[id];
}
}
p->v = -1; //若为结尾，则将v改成-1表示
}
利用树查找：
以查找一个前缀是否出现过为例
思路
从左往右以此扫描每个字母，顺着字典树往下找，能找到这个字母，往下走，否则结束查找，即没有这个前缀；前缀扫完了，表示有这个前缀。
代码
int search(char *str)
{
int len = strlen(str);
Trie *p = root;
for(int i=0; i<len; ++i)
{
int id = str[i]-'0';
p = p->next[id];
if(p == NULL) //若为空集，表示不存以此为前缀的串
return 0;
if(p->v == -1) //字符集中已有串是此串的前缀
return -1;
}
return -1; //此串是字符集中某串的前缀
}
实战
字典树
模板题
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct ooo
{
int next[26];
bool mark; //标记
}dd[505555];
int top,n,m;
char a[20],b[20];
int creat() //分配新的节点
{
memset(dd[top].next,-1,sizeof(dd[top].next)); //表示指向空
dd[top].mark=false;//表示无对应字符串
return top++;
}
int xiab(char c)
{
return c-'a'; //对应下标
}
void insert(int root,char *s) //将S插入到字典树中
{
int i,len=strlen(s);
for(i=0;i<len;i++)
{
if(dd[root].next[xiab(s[i])]==-1)
dd[root].next[xiab(s[i])]=creat();
root=dd[root].next[xiab(s[i])];
}
dd[root].mark=true;
}
bool search(int root,char *s) //询问是否出现在字典树中
{
for(int i=0;s[i]!='\0';i++)
{
if(dd[root].next[xiab(s[i])]==-1)
return false;
root=dd[root].next[xiab(s[i])];
}
return dd[root].mark;
}
int main()
{
int i,j,root;
while(scanf("%d %d",&n,&m)&&(n||m))
{
top=0;
root=creat();
for(i=0;i<n;i++)
{
scanf("%s",a);
insert(root,a);
}
for(i=0;i<m;i++)
{
scanf("%s",b);
printf("%s\n",search(root,b)?"Yes":"No");
}
}
return 0;
}
思路：
题目要求后缀，反转成前缀即可。
但是...数据量太大，字典树会超时，题目就变成了思维题。
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int N=1e5+10;
int col[N];
int a[N][15];
int flag[N];
int k;
string s1,s2;
void Insert()
{
int p=0,i;
for(i=0;i<s1.size();i++)
{
if(!a[p][s1[i]-'0']) a[p][s1[i]-'0']=++k;
col[p]++;//记录几个单词经过了他。
p=a[p][s1[i]-'0'];
}
flag[p]=1;//表示这是一个单词的末尾。
}
int search1()
{
int p=0,i;
for(i=0;i<s2.size();i++)
{
if(!a[p][s2[i]-'0']) return 0;
p=a[p][s2[i]-'0'];
}
return col[p];
}
int main()
{
int n,m,i;
ios::sync_with_stdio(false);
while(cin>>n)
{
for(i=1;i<=n;i++)
{
cin>>s1;
reverse(s1.begin(),s1.end());
Insert();
}
cin>>m;
for(i=1;i<=m;i++)
{
cin>>s2;
reverse(s2.begin(),s2.end());
int num=search1();//找到单词段然后返回值。
printf("%d\n",num);
}
memset(flag,0,sizeof(flag));
memset(a,0,sizeof(a));
memset(col,0,sizeof(col));
k=0;//初始化。
}
return 0;
}