字典树Trie求前缀子串
#include <cstdio> #include <cstdlib> #include <cstring> const int MAXN = 26; struct Trie { // 代表当前节点可以延伸出的边，数量可变 Trie *Next[MAXN]; // 标记当前节点是否是保存信息的结尾，也可以代表前缀个数 int Flag; Trie() { // 初始化以该信息为前缀的信息个数 Flag = 1; memset(Next, NULL, sizeof(Next)); } }*root; void Insert(char *str) { int len = strlen(str); Trie *p = root, *q; // 将str的每一个字符插入trie树 for(int i=0; i<len; ++i) { int id = str[i] - 'a'; // 如果没有边，则新建一个trie节点，产生一条边，用以代表该字符 if(p->Next[id] == NULL) { q = new Trie(); p->Next[id] = q; p = p->Next[id]; } // 如果存在边，则沿着该边走 else { p = p->Next[id]; // 累加以该信息为前缀的信息个数 ++(p->Flag); } } } int Query(char *str) { int len = strlen(str); Trie *p = root; // 在trie树上顺序搜索str的每一个字符 for(int i=0; i<len; ++i) { int id = str[i] - 'a'; p = p->Next[id]; // 若为空集，表示不存以此为前缀的信息 if(p == NULL) return 0; } // 返回以该信息为前缀的信息个数 return p->Flag; } void Free(Trie* T) { if(T == NULL) return; // 释放trie树的每一个节点占用的内存 for(int i=0; i<MAXN; ++i) { if(T->Next[i]) Free(T->Next[i]); } delete(T); } int main() {//freopen("sample.txt", "r", stdin); char str[15]; // 创建trie树的根节点 root = new Trie(); while(gets(str) && str[0]!='\0') { Insert(str); } while(~scanf("%s", str)) { printf("%d\n", Query(str)); } Free(root); return 0; }
