字符串的多模匹配，KMP，字典树，AC自动机，现在学习字典树；
概念：
字典树又称为单词查找树，用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频的统计。优点是利用字符串的公共前缀来减少查询时间，最大限度减少无畏字符串比较，查询效率比哈希树高。
其实字典树就是DFA！！，每层是一个状态，只不过我觉得这棵树的空间利用率不高罢了（HDU1251，G++MLE怨念ing）。
性质：
1.根节点不包含字符，根节点外每个节点都只包含一个字符
2.根节点到某一节点上，路径上经过的字符拼接起来，为该节点对应的字符串；
3.每个节点的所有子节点包含的字符都不相同。
基本操作：查找，插入，删除（少见）
实现方法：
1.从根节点开始一次搜索。
2.取得要查找关键字的第一个字母，并根据该字母选择对应的子树并转到该子树进行检索
3.相应子树上，取得要查找关键词的第二个字母，并进行进一步选择对应的子树进行检索。
4.迭代
5. 某个节点处，关键词的所有字母已被取出，则读取附在该节点上的信息，即完成查找。
应用：
1.串的快速检索：给出N个单词组成的熟词表，以及一篇全用小写英文写的文章，按照最早出现的顺序写出所有不在熟词表中的生词。
2. 串的排序：给定N个互不相同的仅有一个单词构成的英文名，让你将他们安字典序大小，从小到大输出。用字典树进行排序，采用数组的方式创建创建字典树，这棵树的每个节点的所有子节点很显然按照其字母大小排序，对这棵树进行先序遍历即可。
3.最长公共前缀：对所有串建立字典树，对于两个串的最长公共前缀的长度，即他们所在节点的公共祖先个数，于是，问题转外化为当时公共祖先问题。
4.学习自动机的热身
代码实现：
首先是一个板子:
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define Pair pair<int,int>
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))// 水印
//std::ios::sync_with_stdio(false);
// register
const int MAXN=1e3+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll mod=1e9+7;
const double PI=acos(-1.0);
//---------------------------
const int maxn=26;//假设只有小写字母
const int maxm=1e5+10;
struct treenode{
int count;//表示该节点所表示字符串在所有字符串中以前缀形式出现的总次数。
treenode *next[maxm];
}head;
int charmapping[256];//字符映射数组，charmapping[i]=x表示字符i对应于treenode中的next[x]
void init_charmapping(){
for(int i='a';i<='z';++i){
//该字典树只允许输入小写字符组成的字符串 ,
//如果想要增加新字符，添加映射并增大maxn 即可。
charmapping[i]=i-'a';
}
}
void init_trie(){
head.count=1;//初始化为1，包括空串&&避免树头被删除
for(int i=0;i<maxn;++i){
head.next[i]=NULL;
}
}
treenode* createnew(){//申请一个新节点并初始化
treenode* newnode;
newnode=(treenode*)malloc(sizeof(treenode));
newnode->count=0;
for(int i=0;i<maxn;++i){
newnode->next[i]=NULL;
}
return newnode;
}
void updata(char *s,int num){//向字典树中添加num个字符串s
int k=0,temp;
treenode* t=&head;
while(s[k]){//该字符存在
t->count+=num;//此时的节点作为前驱被访问的次数++
temp=charmapping[s[k]];//temp对应该节点的map映射的值
if(t->next[temp]==NULL)//该映射为空
t->next[temp]=createnew();//申请，加入
t=t->next[temp];//向后指
k++;//遍历下一个字符
}
t->count+=num;//以该字符串为前驱的再加num个。
}
int search(char *s,int num){//查找字符串中是否存在num和s
int k=0,temp;
treenode* t=&head;
while(s[k]){
temp=charmapping[s[k]];
if(t->next[temp]==NULL||t->next[temp]->count<num)
return 0;//小于num
t=t->next[temp];
k++;
}
//这里只是单纯的查找字符串s，后面不能多，前面不能少。
int snum=t->count;//最后存在的 个数
for(int i=0;i<maxn;++i){//遍历maxn个字符
if(t->next[i]){//如果这个元素后面有该字符
snum-=t->next[i]->count;//减去后面存在的字符数。
}
}
if(snum>=num){//仍然符合要求
return 1;
}
return 0;
}
void erase(char *s,int num){//删除字典树中nun个s字符串，并将无用的节点释放
int k=0,temp;
treenode* t=&head;
treenode* t1;
head.count-=num;//根节点减少num个
while(s[k]){
temp=charmapping[s[k]];
t->next[temp]->count-=num;//该节点的 子树删掉num个
if(t->next[temp]->count==0){//删干净了。
t1=t->next[temp];
t->next[temp]=NULL;
k++;
break;
}
t=t->next[temp];
k++;
}
while(s[k]){
temp=charmapping[s[k]];
t=t1->next[temp];
free(t1);
t1=t;
k++;
}
free(t1);
}
char temp[1000];
void printall(treenode* tnode,int pos){//递归打印字典树，打出来就是字典序升序排列
int count=tnode->count;
for(int i=0;i<maxn;++i){
if(tnode->next[i])
count-=tnode->next[i]->count;
}
for(int i=0;i<count;++i){
cout<<temp<<endl;
}
for(int i='a';i<='z';++i){
if(tnode->next[charmapping[i]]){
temp[pos]=i;
temp[++pos]='\0';
printall(tnode->next[charmapping[i]],pos);
temp[--pos]='\0';
}
}
}
int main(){
init_charmapping();
init_trie();
char x[1000];
int num,oper;
while(cin>>oper){
if(oper==1){
clean(x,'\0');
cin>>x>>num;
updata(x,num);
}
else if(oper==2){
clean(x,'\0');
cin>>x>>num;
if(search(x,num)==0)
cout<<"No Find"<<endl;
else
cout<<"Yes Find"<<endl;
}
else if(oper==3){
clean(x,'\0');
cin>>x>>num;
erase(x,num);
}
else{
printall(&head,0);
}
}
}
/*
1
apple 1
2
app 1
2
apple 1
1
add 1
4
3
apple 1
4
*/
然后在HDU上找了个板子题：HDU-1251-统计难题：http://acm.hdu.edu.cn/showproblem.php?pid=1251
直接AC：
const int MAXN=28;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll mod=1e9+7;
const double PI=acos(-1.0);
//---------------------------
struct node{
int count;
node *nxt[MAXN];
}tree;
void intt(){
tree.count=1;
for(int i=0;i<MAXN;++i){
tree.nxt[i]=NULL;
}
}
void insert(char *s){
node *t=&tree;
int k=0;
while(s[k]){
t->count++;
if(t->nxt[s[k]-'a']==NULL){
node *p=(node*)malloc(sizeof(node));
p->count=0;
for(int i='a';i<='z';++i){
p->nxt[i-'a']=NULL;
}
t->nxt[s[k]-'a']=p;
}
t=t->nxt[s[k]-'a'];
++k;
}
t->count++;
}
int Query(char *s){
node *t=&tree;
int k=0;
while(s[k]){
if(t->nxt[s[k]-'a']==NULL) return 0;
t=t->nxt[s[k]-'a'];
++k;
}
return t->count;
}
int main(){
intt();
char s[15];
while(gets(s)){
if(s[0]=='\0') break;
//cout<<s<<endl;
insert(s);
clean(s,'\0');
}
while(gets(s)){
if(s[0]=='\0') break;
cout<<Query(s)<<endl;
clean(s,'\0');
}
} 然后还有一道板子：HDU-1075-What Are You Talking About：http://acm.hdu.edu.cn/showproblem.php?pid=1075
大概意思就是首先给你一个一一对应的字典，然后再给你篇文章，你需要按照这个字典里将文章翻译出来，（字典里没有的不需要翻译），字典树+标记就行了，注意一下格式问题，要不然格式错误（我中间加了一个getchar()吃换行。。）
AC：
struct node{
int vis,cnt;
string word;
node *nxt[28];
node():vis(0),cnt(1){
for(int i=0;i<26;++i){
nxt[i]=NULL;
}
}
}root;
void insert(string s1,string s2){//s1对应s2
int l=s1.size();
node *t=&root;
for(int i=0;i<l;++i){
t->cnt++;
if(t->nxt[s1[i]-'a']==NULL){
t->nxt[s1[i]-'a']=new node();
}
t=t->nxt[s1[i]-'a'];
}
t->vis=1;t->word=s2;
}
string Find(string s){
node *t=&root;
int l=s.size();
for(int i=0;i<l;++i){
if(t->nxt[s[i]-'a']==NULL)
return "";
t=t->nxt[s[i]-'a'];
}
string res="";
if(t->vis==1){
res=t->word;
}
return res;
}
int main(){
string s1,s2;
cin>>s1;
while(cin>>s1>>s2){
if(s1=="END") break;
insert(s2,s1);
}
char ch=getchar();//我在这个地方加一个换行
char s[3100]={'\0'};
while(gets(s)){
if(s[0]=='E') break;
string e="";
int k=0;
while(s[k]!='\0'){
if(s[k]>'z'||s[k]<'a'){
string ans=Find(e);
if(ans.size()==0) cout<<e;
else cout<<ans;
e="";cout<<s[k++];continue;
}
e+=s[k++];
}
cout<<endl;
}
}
京公网安备 11010502036488号