首页 > 代码库 > hdu--2846--字典树<怪我思维不够跳跃>
hdu--2846--字典树<怪我思维不够跳跃>
这题 一眼望去 又TM想用map了。。
想起自己已经学过 字典树了 这题 需要拆分出给的字符串的每个子串 还是蛮麻烦的
然后就是再去匹配查找了
其实 这题 我觉得难点是再有没有想到将字符串拆分成子串进行create
想到了这点 还有一点 就是你怎么判断重一性 <可能记错了> 或者说 假如有个字符串aabb那么你可以拆成a a b b aa ab bb aab abb aabb但是对于a的数量只应该+1次 而不是2次
b也同样。。
我说到这了 可能你想到了....bingo 我们需要一个flag标记变量
--------看上面说的狠轻松 2把LOL打完 我TM地才想到 flag标记变量来做
我这题 还是用的动态版字典树 写起来实在太方便了啊。。
我待会 再贴份 静态版的上来 先去次饭 =-=
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 const int size = 26; 6 struct trie 7 { 8 struct trie* next[size]; 9 int cnt;10 int flag;11 };12 trie* root;13 void init( )14 {15 root = new trie;16 for( int i = 0 ; i<size ; i++ )17 {18 root->next[i] = NULL;19 root->cnt = 0;20 root->flag = -1;21 }22 }23 24 void create( char* str , int len , int flag)25 {26 trie* p =root;27 trie* q;28 for( int i = 0 ; i<len ; i++ )29 {30 int id = str[i] - ‘a‘;31 if( p->next[id] == NULL )32 {33 q = new trie;34 for( int i = 0 ; i<size ; i++ )35 {36 q->next[i] = NULL;37 q->cnt = 0;38 q->flag = -1;39 }40 p->next[id] = q;41 }42 p = p->next[id];43 }44 if( p->flag!=flag )45 {46 p->flag = flag;47 p->cnt ++;48 }49 }50 51 int find( char* str )52 {53 trie* p = root;54 int len = strlen(str);55 for( int i = 0 ; i<len ; i++ )56 {57 int id = str[i] - ‘a‘;58 if( p->next[id] == NULL )59 {60 return 0;61 }62 p = p->next[id];63 }64 return p->cnt;65 }66 67 int main()68 {69 cin.sync_with_stdio(false);70 int n , m , len;71 char str[25];72 init( );73 cin >> n;74 while( n-- )75 {76 cin >> str;77 len = strlen(str);78 for( int i = 0 ; i<len ; i++ )79 {80 for( int j = 1 ; i+j<=len ; j++ )81 {82 create( str+i , j , n);83 }84 }85 }86 cin >> m;87 while( m-- )88 {89 cin >> str;90 cout << find(str) << endl;91 }92 return 0;93 }
静态版的 写起来 就是麻烦了点 但是速度也没快多少啊=-= 难道是我写的太差嘛
#include <iostream>#include <cstring>using namespace std;int sum = 0;const int size = 26;const int num = 1000010;struct trie{ int next[size]; int cnt; int flag;};trie node[num];void init( int root ){ for( int i = 0 ; i<size ; i++ ) { node[root].next[i] = -1; node[root].cnt = 0; node[root].flag = -1; }}void create( char* str , int len , int flag){ int root = 0; for( int i = 0 ; i<len ; i++ ) { int id = str[i] - ‘a‘; if( node[root].next[id] == -1 ) { node[root].next[id] = ++sum; init( sum ); root = sum; } else { root = node[root].next[id]; } } if( node[root].flag!=flag ) { node[root].flag = flag; node[root].cnt ++; }}int find( char* str ){ int root = 0; int len = strlen(str); for( int i = 0 ; i<len ; i++ ) { int id = str[i] - ‘a‘; if( node[root].next[id] == -1 ) { return 0; } root = node[root].next[id]; } return node[root].cnt;}int main(){ cin.sync_with_stdio(false); int n , m , len; char str[25]; init(0); cin >> n; while( n-- ) { cin >> str; len = strlen(str); for( int i = 0 ; i<len ; i++ ) { for( int j = 1 ; i+j<=len ; j++ ) { create( str+i , j , n); } } } cin >> m; while( m-- ) { cin >> str; cout << find(str) << endl; } return 0;}
today:
你能用 一句话总结自己过去的10年吗？
十年前总是计划着十年后
十年后时刻回忆着十年前
-------扯淡
以我20岁而言
十年前 才10岁 还在玩捉迷藏了
十年后 才30岁 不知道在干什么了
----------开心就好
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。