/*字典序模板*/ #define MAX 26 //每层有多少种类 typedef struct trie { trie *next[MAX]; int v;//一个字典树到此有多少相同前缀的数目 }; trie *root; void creat_trie(char *str) { int len=strlen(str); trie *p=root,*q; for(int i=0;i<len;i++) { int id=str[i]-'a'; if(p->next[id]==NULL) { q=(trie*)malloc(sizeof(trie)); q->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; } int find_trie(char *str) { int len=strlen(str); trie *p=root; for(int i=0;i<len;i++) { int id=str[i]-'a'; p=p->next[id]; if(p==NULL) return 0; if(p->v==-1) return -1; } return -1; } //超内存怎么办? //释放空间 void clear_trie(trie *t) { if(t==NULL) //空树直接返回 return ; for(int i=0;i<MAX;i++) { if(t->next[i]!=NULL)
clear_trie(t->next[i]);
}
free(t);
}
静态数组写法模板
child[p][id]表示第p号前缀后面加一个“id”代表的字符形成的前缀是第几号前缀。为-1表示原字典树中不存在此前缀。
int tot=0; void insert(char* ch) { int p = 0, l = strlen(ch + 1); for (int i = 1; i <= l; i++) { if (child[p][ch[i] - 'a'] == -1) child[p][ch[i] - 'a'] = ++tot; p = child[p][ch[i] - 'a']; } }