首页 > 代码库 > 字典树的动态与静态模板
字典树的动态与静态模板
动态链表:
#include <iostream> #include <cstdio> #include <cstring> #include <cstring> using namespace std; struct Node { Node * child[10]; bool bad; Node() //构造函数中初始化。在静态分配时就能初始化。 { memset(child, 0, sizeof(child)); bad = false; } }; int nodeCount; //用来指向数组中未分配的单元。 bool insertNode(Node *tree, char *s) { int i; Node * p = tree; for(i = 0; s[i+1]; i++) { if(p->child[s[i]-‘0‘] == 0) { p->child[s[i]-‘0‘] = tree + nodeCount; //将各个节点按次序分配到数组的相应位置。 nodeCount++; } p = p->child[s[i]-‘0‘]; if(p->bad) //如果遇到危险节点(某个字符串的最后一个节点),则说明该串含有前面的串。 { return false; } } bool ok; if(p->child[s[i]-‘0‘] == 0) { p->child[s[i]-‘0‘] = tree + nodeCount; nodeCount++; ok = true; } else //如果最后一个节点已经被分配过,说明该串是前面串的前缀。 ok = false; p = p->child[s[i]-‘0‘]; p->bad = true; //字符串最后一个节点是危险节点。 return ok; } void del(Node *p) { for(int i=0;i<10;i++) { if(p->child[i]) del(p->child[i]); } delete(p); } Node Tree[100000]; //为了避免初始化,直接重新开,分配大小要合适,否则RA。 int main() { int n, i, t; bool ok; scanf("%d", &t); while(t--) { scanf("%d", &n); char s[12]; memset(Tree,0,sizeof(Tree)); nodeCount = 1; ok = true; for(i = 0; i < n; i++) { scanf(" %s", s); if(!insertNode(Tree, s)) { ok = false; } } if(ok) printf("YES\n"); else printf("NO\n"); } return 0; }
静态数组模拟模板:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int M = 33333; const int N = 27; char st[M][N]; int tot,size,sz; int trie[M*10][N],num[10*M]; void insert(char *st){ int len=strlen(st+1); int now=0; for(int i=1;i<=len;i++){ int k=st[i]-‘a‘; if(trie[now][k]==0) trie[now][k]=++sz; now=trie[now][k]; num[now]++; } } void ask(char *st){ int now=0,k,len=strlen(st+1); for(int i=1;i<=len;i++){ if(num[now]==1) break; k=st[i]-‘a‘; printf("%c",st[i]); now=trie[now][k]; } } int main(){ while(~scanf("%s",st[++tot]+1)) insert(st[tot]); for(int i=1;i<=tot;i++){ printf("%s ",st[i]+1); ask(st[i]); printf("\n"); } return 0; }
字典树的动态与静态模板
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。