Trie树与Trie图的学习

Trie树

   Trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串（通常而已）。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。每个键标注在节点中，附加信息在节点之下。每个键代表的不是字符（数字），而是字符串（数列） 。

  看了某前辈的博客，得知白书上有Trie树的讲解，发现也不是太详细，然后根据其博客整理学习了一下，大概了解这个套路了

  ch[maxnode][sigma_size] sigma_size = 26，对应全部的小写字母 用ch[i][j]表示结点i的对应编号j的子结点。（难懂） val[i]代表单词结点上的附加信息，例如权值等等

struct Trie { int ch[N][sigma_size]; int val[N],sz; Tree() { sz=1;//当前节点数量 memset(ch[0],0,sizeof(ch[0])); } int idx(char c){return c-'a';} //插入 void Insert(char *s,int v) { int u=0,len=strlen(s); for(int i=0;i<len;i++) { int c=(idx(s[i])); if(!ch[u][c])//结点不存在 { memset(ch[sz],0,sizeof(ch[sz])); val[sz]=0;//附加信息 ch[u][c]=sz++;//新建结点，给其编号 } u=ch[u][c];//往下走 } val[u]=v; } } 然后a了hihocoder1014 : Trie树

#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N = 1000005; const int sigma_size = 26; struct Trie { int ch[N][sigma_size]; int val[N],sz; void Init() { sz=1;//当前节点数量 memset(ch[0],0,sizeof(ch[0])); } int idx(char c){return c-'a';} //插入 void Insert(char *s) { int u = 0,len = strlen(s); for(int i = 0;i < len;i++) { int c=(idx(s[i])); if(!ch[u][c])//结点不存在 { memset(ch[sz],0,sizeof(ch[sz])); val[sz]=1;//附加信息1 ch[u][c]=sz++;//新建结点，给其编号 u = ch[u][c];//往下走 } else//已经存在 { u=ch[u][c];//往下走 val[u]++;//计数加加 } } } //查询 int Query(char *s) { int u = 0,len = strlen(s); //一直向下走，直到找到所给前缀的最后一个单词 for(int i = 0;i < len;i++) { int c = idx(s[i]); if(ch[u][c]) u = ch[u][c]; else//无法匹配 return 0; } return val[u]; } }; Trie T; int main() { int n,m; char str[15]; while(~scanf("%d",&n)) { T.Init(); for(int i = 1;i <= n;i++) { scanf("%s",str); T.Insert(str); } scanf("%d",&m); for(int i = 1;i <= m;i++) { scanf("%s",str); printf("%d\n",T.Query(str)); } } return 0; }

HDU-4825 Xor Sum

利用Trie树，参考的另一种代码

Here

HDU-5687

这个用的链表的方法，删除时候注意，要先查询出前缀可以匹配的个数num，再进行删除

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; const int Letters = 26; int idx(char s){return s - 'a';} struct Trie { int cnt; Trie *next[Letters]; Trie() { cnt = 0; memset(next,0,sizeof(next)); } }; Trie *root; void Insert(char *word) { Trie *tmp = root; for(int i = 0;word[i] != '\0';i++) { int x = idx(word[i]); if(tmp->next[x] == NULL)//结点不存在 tmp->next[x] = new Trie; tmp = tmp->next[x]; tmp->cnt++; } } int Search(char *word) { Trie *tmp = root; for(int i = 0;word[i] != '\0';i++) { int x = idx(word[i]); if(tmp->next[x] == NULL)//无法匹配 return 0; tmp = tmp->next[x]; } return tmp->cnt; } void Delete(char *word,int num) { Trie *tem = root; for(int i = 0;word[i] != '\0';i++) { int x = idx(word[i]); tem = tem->next[x]; tem->cnt -= num; } for(int i = 0;i < Letters;i++) tem->next[i] = NULL; } int main() { int n; cin >> n; char s[20],str[50]; root = new Trie;//别忘了申请内存，防止野指针 while(n--) { scanf("%s %s",s,str); if(s[0] == 'i') { Insert(str); } else if(s[0] == 's') { if(Search(str)) printf("Yes\n"); else printf("No\n"); } else { int num = Search(str); if(num) Delete(str,num); } } return 0; }

HDU-1251

注意输入即可

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; inline int idx(char c){return c -'a';} struct Trie { int cnt; Trie *next[26]; Trie() { cnt = 0; memset(next,0,sizeof(next)); } }; Trie *root; void Insert(char *word) { Trie *tmp = root; for(int i = 0;word[i] != '\0';i++) { int x= idx(word[i]); if(tmp->next[x] == NULL) tmp->next[x] = new Trie; tmp = tmp->next[x]; tmp->cnt++; } } int Search(char *word) { Trie *tmp = root; for(int i = 0;word[i] != '\0';i++) { int x = idx(word[i]); if(tmp->next[x] == NULL) return 0; tmp = tmp->next[x]; } return tmp->cnt; } int main() { char str[20]; root = new Trie; while(gets(str))//要读入空 { if(strcmp(str,"") == 0) break; Insert(str); } while(scanf("%s",str) != EOF) printf("%d\n",Search(str)); return 0; }

Trie图（DFA）、AC自动机

  AC自动机是基于多串匹配的算法，其思想基于Trie树和KMP算法，故其又名Trie图。   在Trie树的基础上，加上前缀指针，前缀指针的作用是匹配失败时跳转到与当前串具有最长公共前后缀的的字符继续进行匹配，这点和KMP算法的next数组作用是类似的，所以前缀指针又叫做失败指针。跳转后的前缀必须是跳转前的后缀，即深度减小了。   前缀指针的构造：要求是通过bfs的方法进行对每一个前缀指针的求解。对于当前节点，求其前缀指针，设其与其父节点间的字符为a，然后找到其父节点的前缀指针（已知的），对其子节点中寻找同为字符a的下节点（较深的节点），然后当前节点的前缀指针就指向了这儿。如果没有这个符合条件的节点，则深度继续向上，找当前节点父节点的前缀指针所指节点的前缀指针的所指节点，描述不清楚了，直至根节点，熟透了再更一次吧。   遍历：首先要知道终止节点是危险节点，而前缀指针指向危险节点相连的节点也是危险节点。从根节点开始遍历，如果开始不匹配的情况，就寻找前缀指针指向的节点，后面依此寻找，如果找到了终止节点，说明原串肯定包含该节点代表的模式串。如果找到了危险节点，则继续寻找终止节点。(能力有限，还不能清楚描述)

最纯粹的Trie图题目

给N个模式串，每个不超过个字符，再给M个句子，句子长度<100 判断每个句子里是否包含模式串N < 10, M < 10 ,字符都是小写字母

样例

5 8 abcde defg cdke ab f abcdkef abkef bcd bca add ab qab f

代码：

#include<iostream> #include<cstdio> #include<cstring> #include <vector> #include <queue> using namespace std; const int Letters = 26; int nnodescount = 0; struct cnode { cnode * pChilds[Letters]; cnode * pPrev; //前缀指针 bool bBadNode; //是否是危险节点 void Init() { memset(pChilds,0,sizeof(pChilds)); bBadNode = false; pPrev = NULL; } }Tree[200];//10个模式串，每个10个字符，每个字符一个节点，也只要100个节点 //将模式串s插入trie树 void Insert( cnode * pRoot, char * s) { for(int i = 0; s[i];i++) { if(pRoot->pChilds[s[i]-'a'] == NULL) { pRoot->pChilds[s[i]-'a'] = Tree + nnodescount; nnodescount ++; } pRoot = pRoot->pChilds[s[i]-'a']; } pRoot-> bBadNode = true; } //在trie树上加前缀指针 void BuildDfa() { for(int i = 0;i < Letters;i++) Tree[0].pChilds[i] = Tree + 1; Tree[0].pPrev = NULL; Tree[1].pPrev = Tree; deque<cnode * > q; q.push_back(Tree+1); while(!q.empty()) { cnode * pRoot = q.front(); q.pop_front(); for(int i = 0;i < Letters;i++) { cnode * p = pRoot->pChilds[i]; if(p) { cnode * pPrev = pRoot->pPrev; while( pPrev ) { if( pPrev->pChilds[i] ) { p->pPrev = pPrev->pChilds[i]; if( p->pPrev-> bBadNode) p-> bBadNode = true; //自己的pPrev指向的节点是危险节点，则自己也是危险节点 break; } else pPrev = pPrev->pPrev; } q.push_back(p); } } } //对应于while( ! q.empty() ) } //返回值为true则说明包含模式串 bool SearchDfa(char * s) { cnode * p = Tree + 1; for(int i = 0; s[i] ;i++) { while(true) { if(p->pChilds[s[i]-'a']) { p = p->pChilds[s[i]-'a']; if( p-> bBadNode) return true; break; } else p = p->pPrev; } } return false; } int main() { nnodescount = 2; int m,n; scanf("%d%d",&n,&m); //N个模式串， M个句子 for(int i = 0;i < n;i ++ ) { char s[20]; scanf("%s",s); Insert(Tree + 1,s); } BuildDfa(); for(int i = 0;i < m;i ++) { char s[200]; scanf("%s",s); cout << SearchDfa(s) << endl; } return 0; } //（纯属摘抄）

  上面的代码稍微修改一下就可以AChihocoder1036了

#include<iostream> #include<cstdio> #include<cstring> #include <vector> #include <queue> using namespace std; const int Letters = 26; const int N = 2000005; int nnodescount = 0; struct cnode { cnode * pChilds[Letters]; cnode * pPrev; //前缀指针 bool bBadNode; //是否是危险节点 void Init() { memset(pChilds,0,sizeof(pChilds)); bBadNode = false; pPrev = NULL; } }Tree[N];//10个模式串，每个10个字符，每个字符一个节点，也只要100个节点 //将模式串s插入trie树 void Insert( cnode * pRoot, char * s) { for(int i = 0; s[i];i++) { if(pRoot->pChilds[s[i]-'a'] == NULL) { pRoot->pChilds[s[i]-'a'] = Tree + nnodescount; nnodescount ++; } pRoot = pRoot->pChilds[s[i]-'a']; } pRoot-> bBadNode = true; } //在trie树上加前缀指针 void BuildDfa() { for(int i = 0;i < Letters;i++) Tree[0].pChilds[i] = Tree + 1; Tree[0].pPrev = NULL; Tree[1].pPrev = Tree; deque<cnode * > q; q.push_back(Tree+1); while(!q.empty()) { cnode * pRoot = q.front(); q.pop_front(); for(int i = 0;i < Letters;i++) { cnode * p = pRoot->pChilds[i]; if(p) { cnode * pPrev = pRoot->pPrev; while( pPrev ) { if( pPrev->pChilds[i] ) { p->pPrev = pPrev->pChilds[i]; if( p->pPrev-> bBadNode) p-> bBadNode = true; //自己的pPrev指向的节点是危险节点，则自己也是危险节点 break; } else pPrev = pPrev->pPrev; } q.push_back(p); } } } //对应于while( ! q.empty() ) } //返回值为true则说明包含模式串 bool SearchDfa(char * s) { cnode * p = Tree + 1; for(int i = 0; s[i] ;i++) { while(true) { if(p->pChilds[s[i]-'a']) { p = p->pChilds[s[i]-'a']; if( p-> bBadNode) return true; break; } else p = p->pPrev; } } return false; } int main() { nnodescount = 2; int n; char s[N]; scanf("%d",&n); //N个模式串， M个句子 for(int i = 0;i < n;i ++ ) { scanf("%s",s); Insert(Tree + 1,s); } BuildDfa(); //char s[N]; scanf("%s",s); if(SearchDfa(s)) cout << "YES" << endl; else cout << "NO" << endl; return 0; } //（纯属摘抄）   思考良久，还是换飘过的小牛的模板吧，和我学的Trie树的方法非常相像，用起来也更顺手。

HDU-2222

#include<iostream> #include<cstdio> #include<cstring> #include<string> using namespace std; #define N 1000010 char str[N], keyword[N]; int head, tail; struct Trie { Trie *fail; Trie *next[26]; int count; Trie() //init { fail = NULL; count = 0; for(int i = 0; i < 26; ++i) next[i] = NULL; } }*q[N]; Trie *root; void Insert(char *str) //建立Trie { int temp, len; Trie *p = root; len = strlen(str); for(int i = 0; i < len; ++i) { temp = str[i] - 'a'; if(p->next[temp] == NULL) p->next[temp] = new Trie(); p = p->next[temp]; } p->count++; } void Build_ac() //初始化fail指针，BFS { q[tail++] = root; while(head != tail) { Trie *p = q[head++]; //弹出队头 Trie *temp = NULL; for(int i = 0; i < 26; ++i) { if(p->next[i] != NULL) { if(p == root) //第一个元素fail必指向根 p->next[i]->fail = root; else { temp = p->fail; //失败指针 while(temp != NULL) //2种情况结束：匹配为空or找到匹配 { if(temp->next[i] != NULL) //找到匹配 { p->next[i]->fail = temp->next[i]; break; } temp = temp->fail; } if(temp == NULL) //为空则从头匹配 p->next[i]->fail = root; } q[tail++] = p->next[i]; //入队 } } } } int Query() //扫描 { int index, len, result; Trie *p = root; //Tire入口 result = 0; len = strlen(str); for(int i = 0; i < len; ++i) { index = str[i] - 'a'; while(p->next[index] == NULL && p != root) //跳转失败指针 p = p->fail; p = p->next[index]; if(p == NULL) p = root; Trie *temp = p; //p不动，temp计算后缀串 while(temp != root && temp->count != -1) { result += temp->count; temp->count = -1; temp = temp->fail; } } return result; } int main() { int t,num; cin >> t; while(t--) { head = tail = 0; root = new Trie(); scanf("%d", &num); getchar(); for(int i = 0; i < num; ++i) { scanf("%s",keyword); Insert(keyword); } Build_ac(); scanf("%s", str); printf("%d\n",Query()); } return 0; }