首页 > 代码库 > Trie树
Trie树
字典树查询
#include<iostream> #include<cstring> #include<malloc.h> using namespace std; const int maxn = 30; typedef struct Trie{ int v; Trie *next[ maxn ]; }Trie; Trie root; void CreateTrie( char *str ){ int len = strlen( str ); //cout << str << endl; Trie *p = &root, *q; for( int i = 0; i < len; ++i ){ int id = str[ i ] - 'a'; if( p -> next[ id ] == NULL ){ //q = new Trie; q = ( Trie * )malloc( sizeof( root ) ); for( int j = 0; j < maxn; ++j ){ q -> next[ j ] = NULL; } q -> v = 1; p -> next[ id ] = q; } else{ p -> next[ id ] -> v++; } p = p -> next[ id ]; } } int FindTrie( char *str ){ int len = strlen( str ); Trie *p = &root; for( int i = 0; i < len; ++i ){ int id = str[ i ] - 'a'; if( p -> next[ id ] == NULL ){ return 0; } p = p -> next[ id ]; } return p -> v; } int main(){ int n, m; char str[ maxn ]; for( int i = 0; i < maxn; ++i ){ root.next[ i ] = NULL; } cin >> n; while( n-- ){ cin >> str; CreateTrie( str ); } memset( str, 0, sizeof( str ) ); cin >> m; while( m-- ){ cin >> str; int ans = FindTrie( str ); cout << ans << endl; } return 0; } /* 5 banana band bee absolute acm 4 ba b band abc 2 3 1 0 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。