首页 > 代码库 > Trie树沉思录(1)
Trie树沉思录(1)
发现自己已经很久没有写解题报告了,很大一部分是因为懒,做完题之后不想再怎样了~不过最近发现写解题报告确实是有好处的,一方面可以复习,一方面可以梳理。还有就是可以给自己的岁月留下一点什么东西~今天是五一劳动节,就应该要劳动!我要重新着手写我的博客了~
最近几个星期都在研究字符串,有点难,不过到现在为止Trie数学得还算是有那么点意思,写篇博文来记录一下!
(关于Trie数是什么东西我就不想写了,我只写我个人的一些思考)
Trie树通过共享前缀来达到了节约内存的目标,十分的强大!关于他的实现大概有两种:指针和二维数组!我自己学的是白书上面的二维数组。关于两种的区别,据航姐姐说,对于题目只有一组测试数据的,那种都可以,对于有多重测试数据的,二维数组比较好,以为在初始化比较的方便!接下来我具体地说一下二维数组的实现细节!
二维数组的实现个人觉得非常的强大!他充分利用了二维数据的各个部分进行数据存储!我们假设一个二维数组ch[i][j] = k,那么他的各部分的意思解释如下:
i :当前节点的父节点的编号
j:当前节点的字符对应的数字的值;
k:当前节点的编号
为了记录当前节点是否为单词的结尾,我们引入了一个新的数组val[],如果当前节点是单词的结尾,值为1,否则为0,这样我们就可以非常高效的判断某一个单词的结尾了~
对于插入和寻找的细节,我打算在代码中注释给大家~
接下来我们来看几道题:
HDOJ 1251:http://acm.hdu.edu.cn/showproblem.php?pid=1251
经典的入门题:
给你一堆单词,然后后面给一些前缀,问你以这些前缀为开头的单词有多少个?
#include <iostream> #include <cstring> #include <cstdio> #define N 26 #define M 1000000 using namespace std; int ch[M][N];//trie树 int val[M];//记录当前的节点是否为单词的结尾 int sub[M];//记录以当前节点为前缀的单词的次数 int allnode;//节点总数 void initial( ) { memset( val, -1, sizeof( val ) ); memset( sub, 0, sizeof( sub ) ); memset( ch[0], 0, sizeof( ch[0] ) ); allnode = 1;//一开始只有根节点 } int trans( char c ) { return c - ‘a‘; } void Insert( char *s, int v ) { int curnode = 0;//所有单词的一开始都是以根节点为父节点的 int len = strlen( s ); for( int i = 0; i < len; i++ ) { int c = trans( s[i] ); if( !ch[curnode][c] )//节点不存在,开辟新的节点 { memset( ch[allnode], 0, sizeof( ch[allnode] ) );//开辟以当前节点为父节点的ch数组并初始化 val[allnode] = 0;//开辟一个新的结尾数组 ch[curnode][c] = allnode++;//新节点的编号就是当前的节点数 } curnode = ch[curnode][c];//不管用不用新建节点,都要更新父节点 sub[curnode]++;//放在上一句的后面是为了避免根节点 } val[curnode] = v;//最后跳出循环的curnode和allnode一定相等,将一个非零的值付给最后一个节点的val数组 //printf( "w" ); } int Find( char *s )//寻找过程与插入十分地接近 { //printf( "w" ); int len = strlen( s ); int curnode = 0;//一开始还是以根节点开始 //cout << len << endl; for( int i = 0; i < len; i++ ) { int c = trans( s[i] ); if( !ch[curnode][c] ) { return 0; } else { curnode = ch[curnode][c]; } //该循环是为了找到是否存在当前的前缀,如果存在,找出返回以该前缀的的最后一个字符的sub数组的值就是以该前缀为开始的单词数 } //printf( "w" ); return sub[curnode]; } int main() { //freopen( "in.txt", "r", stdin ); char str[N] = {0}; initial(); int i = 1; while( gets( str ) && str[0] ) { //cout << str << endl; Insert( str, i++ ); } //Find( str ); while( gets( str ) ) { //printf( "wandm"); //puts( str ); printf( "%d\n", Find( str ) ); } }
HDOJ 1671 :http://acm.hdu.edu.cn/showproblem.php?pid=1671
给你一堆电话号码,如果里面没有任何一个是另外一个的前缀,输出yes,否则输出no。
思路:每读入一个电话号码,插入字典树,并进行寻找。这里的寻找有两种情况:长找短,短找长(即当前有可能是前缀要找是有以之为前缀的电话号码,或者是不是前缀,即要在树中找到是否有前缀)。如果是第一种情况,只要在发生失配的时候判断当前的节点是否为结尾即可;第二种情况,只要完全匹配,这说明存在以当前号码为前缀的的号码~
有点啰嗦,看代码:
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #define N 500000 #define M 10 #define CJ -1 using namespace std; int ch[N][M]; int val[N]; int allnode; void initial() { memset( ch[0], 0, sizeof( ch[0] ) ); memset( val, -1, sizeof( val ) ); allnode = 1; } void Insert( char *s, int v ) { int curfather = 0; int len = strlen( s ); for( int i = 0; i < len; i++ ) { if( !ch[curfather][s[i]-‘0‘] ) { memset( ch[allnode], 0, sizeof( ch[allnode] ) ); val[allnode] = 0; ch[curfather][s[i]-‘0‘] = allnode++; } curfather = ch[curfather][s[i]-‘0‘]; } val[curfather] = v; } int Find( char *s )//false means NO, { int len = strlen( s ); int sub = 0; int curfather = 0; for( int i = 0; i < len; i++ ) { if( !ch[curfather][s[i]-‘0‘] ) { if( val[curfather] > 0 ) //当前点为单词的最后一个节点 { return false; } else { return CJ; } } else { curfather = ch[curfather][s[i]-‘0‘]; sub++; } } if( sub == len ) { return false; } else { return CJ; } } int main() { char str[12] = {0}; int t; scanf( "%d", &t ); getchar(); //start: while( t-- ) { int num; //char ans[5] = {0}; bool no = false; scanf( "%d", &num ); //cout << num << endl; getchar(); initial(); for( int i = 1; i <= num; i++ ) { scanf( "%s", str ); //cout << str << endl; if( Find( str ) == false ) { //cout << "NO" << endl; //strcmp( ans, "NO" ); no = true; continue; //goto start; } else { if( !no ) { Insert( str, i ); } } } if( no ) { cout << "NO" << endl; } else { cout << "YES" << endl; } //cout << "YES" << endl; } return 0; }
本来还做了另一道题的,不过一直WA,也不知道是为什么?争取今天把它A了~
那就先这样吧~
这三天对我很重要!!!