• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    迪恩网络公众号

C++ TrieNode类代码示例

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

本文整理汇总了C++中TrieNode的典型用法代码示例。如果您正苦于以下问题:C++ TrieNode类的具体用法?C++ TrieNode怎么用?C++ TrieNode使用的例子?那么恭喜您, 这里精选的类代码示例或许可以为您提供帮助。



在下文中一共展示了TrieNode类的20个代码示例,这些例子默认根据受欢迎程度排序。您可以为喜欢或者感觉有用的代码点赞,您的评价将有助于我们的系统推荐出更棒的C++代码示例。

示例1: insert

static inline void
insert(TrieNode<CharT, BucketT>* root, unsigned char** strings, size_t n)
{
	for (size_t i=0; i < n; ++i) {
		unsigned char* str = strings[i];
		size_t depth = 0;
		CharT c = get_char<CharT>(str, 0);
		TrieNode<CharT, BucketT>* node = root;
		while (node->is_trie(c)) {
			assert(not is_end(c));
			node = node->get_node(c);
			depth += sizeof(CharT);
			c = get_char<CharT>(str, depth);
		}
		BucketT* bucket = node->get_bucket(c);
		assert(bucket);
		bucket->push_back(str);
		if (is_end(c)) continue;
		if (bucket->size() > Threshold) {
			node->_buckets[c] = BurstImpl()(*bucket,
					depth+sizeof(CharT));
			make_trie(node->_buckets[c]);
			delete bucket;
		}
	}
}
开发者ID:Komalesh,项目名称:string-sorting,代码行数:26,代码来源:burstsort2.cpp


示例2: insert

void Trie::insert(const std::string& stringToInsert)
{
	TrieNode* currentNode = this->root.get();
	for(auto stringIt = stringToInsert.begin(); stringIt != stringToInsert.end(); ++stringIt)
	{
		char currentChar = *stringIt;

		bool done = false;
		// 2. if there is a node with value == c, set that node as current node. Repeat.
		for (auto it = currentNode->children.begin(); it != currentNode->children.end() && !done; ++it)
		{
			if ((*it)->value == currentChar)
			{
				currentNode = *it;
				done = true;
			}
		}

		if(done)
			continue;

		// 3. if not, insert a node and go to 2.
		currentNode = currentNode->addNode(currentChar);
	}

	currentNode->hasString = true;
}
开发者ID:ThePadawan,项目名称:rosalind,代码行数:27,代码来源:Trie.cpp


示例3: while

  TrieNode *searchPattern(string word) {
    typedef std::pair<TrieNode *, int> Match;
    stack<Match>s;
    s.push(make_pair(root, 0));
    int len = word.length();
    while (!s.empty()) {
      Match m = s.top();
      TrieNode *node = m.first;
      s.pop();

      int id = m.second;
      if (id >= len) {
        if (node->isEnd() || s.empty()) {
          return node;
        }
        continue;
      }

      char ch = word[m.second];
      if (ch == '.') {
        for (int i = 0; i < TrieNode::R; i++) {
          if (node->links[i]) {
            s.push(make_pair(node->links[i], id + 1));
          }
        }
      } else if (node->containsKey(ch)) {
        s.push(make_pair(node->get(ch), id + 1));
      }
    }
    return NULL;
  }
开发者ID:guan78001,项目名称:hello,代码行数:31,代码来源:211_Add+and+Search+Word+-+Data+structure+design.cpp


示例4: addWord

void Dictionary::addWord( const std::string &word )
{
    TrieNode *node = root_;

    int tmp = 0;
    for ( auto it = word.rbegin(); it != word.rend(); ++it )
    {
        char c = *it;
        if ( !isdigit(c) && !isalpha(c) )
        {
            ++tmp;
            continue;
        }
        TrieNode *next_node = node->contain(c); 
        if ( next_node ) 
        {
            node = next_node;    
            continue;
        }
        node = node->addNode(c);
    }
    
    max_length_ = std::max( max_length_, word.size() - tmp );
    if ( node != root_ )
    {
        node->setEndWord(true);
    }
}
开发者ID:honzatran,项目名称:nocr,代码行数:28,代码来源:dictionary.cpp


示例5: reassignKeywordIds

void IndexData::reassignKeywordIds() {
	map<TrieNode *, unsigned> trieNodeIdMapper; //
	this->trie->reassignKeywordIds(trieNodeIdMapper);

	// Generating an ID mapper by iterating through the set of trie nodes whose
	// ids need to be reassigned
	// a map from temperory id to new ids, this map is used for changing forwardIndex and quadTree
	map<unsigned, unsigned> keywordIdMapper;
	for (map<TrieNode *, unsigned>::iterator iter = trieNodeIdMapper.begin();
			iter != trieNodeIdMapper.end(); ++iter) {
		TrieNode *node = iter->first;
		unsigned newKeywordId = iter->second;

		keywordIdMapper[node->getId()] = newKeywordId;

		node->setId(newKeywordId); // set the new keyword Id
	}

	map<unsigned, unsigned> processedRecordIds; // keep track of records that have been converted

	// Now we have the ID mapper.  We want to go through the trie nodes one by one.
	// For each of them, access its inverted list.  For each record,
	// use the id mapper to change the integers on the forward list.
	changeKeywordIdsOnForwardLists(trieNodeIdMapper, keywordIdMapper,
			processedRecordIds);

	// apply the ID mapper on the keyword ids of empty leaf nodes
	this->trie->applyKeywordIdMapperOnEmptyLeafNodes(keywordIdMapper);
}
开发者ID:Poorvak,项目名称:srch2-ngn,代码行数:29,代码来源:IndexData.cpp


示例6: search

 // Returns if the word is in the trie.
 bool search(string word) {
     TrieNode* itr = root;
     for (int i = 0; itr != NULL && i < word.length(); ++i) {
         itr = itr->locateCh(word[i]);
     }
     return (itr != NULL && itr->isWordEnd());
 }
开发者ID:zrss,项目名称:LeetCode,代码行数:8,代码来源:ImplementTrie.cpp


示例7: startsWith

 // Returns if there is any word in the trie
 // that starts with the given prefix.
 bool startsWith(string prefix) {
     TrieNode* itr = root;
     for (int i = 0; itr != NULL && i < prefix.length(); ++i) {
         itr = itr->locateCh(prefix[i]);
     }
     return (itr != NULL);
 }
开发者ID:zrss,项目名称:LeetCode,代码行数:9,代码来源:ImplementTrie.cpp


示例8: boldWords

    string boldWords(vector<string>& words, string S) {
        TrieNode trie;
        for (const auto& word : words) {
            trie.Insert(word);
        }

        vector<bool> lookup(S.length());
        for (int i = 0; i < S.length(); ++i) {
            auto curr = &trie;
            int k = i - 1;
            for (int j = i; j < S.length(); ++j) {
                if (!curr->leaves[S[j] - 'a']) {
                    break;
                }
                curr = curr->leaves[S[j] - 'a'];
                if (curr->isString) {
                    k = j;
                }
            }
            fill(lookup.begin() + i, lookup.begin() + k + 1, true);
        }

        string result;
        for (int i = 0; i < S.length(); ++i) {
            if (lookup[i] && (i == 0 || !lookup[i - 1])) {
                result += "<b>";
            }
            result.push_back(S[i]);
            if (lookup[i] && (i == (S.length() - 1) || !lookup[i + 1])) {
                result += "</b>";
            }
        }
        return result;
    }
开发者ID:BriteSun,项目名称:LeetCode-1,代码行数:34,代码来源:bold-words-in-string.cpp


示例9: printf

////////////////////////////////////////////////////////////////////////////////
// Finds s in the tree and returns the node (may not be a leaf) returns null
// otherwise.
TrieNode* Trie::FindSubStr( const std::string& s )
{
    if( root == NULL ) {
        printf( "ERROR in Trie::FindSubStr, root == NULL!!!!!\n" );
        return NULL;
    }

    if( s.length() == 0 )
        return root;

    TrieNode *traverseNode = root;

    for( unsigned int i = 0 ; i < s.length() ; i++ ){
        traverseNode = traverseNode->TraverseFind( s[i] );
        if( traverseNode ) {
            continue;
        } else {
            return NULL;
        }
    }

    // Look for a leaf node here and return it if no leaf node just return this
    // node.
    std::list<TrieNode*>::iterator it;
    for(it = traverseNode->m_children.begin() ; it != traverseNode->m_children.end() ; it++){
        //found child
        if((*it)->m_nNodeType == TRIE_LEAF) {
            return (*it);
        }
    }

    return traverseNode;
}
开发者ID:arpg,项目名称:CVars,代码行数:36,代码来源:Trie.cpp


示例10: random_sample

static TrieNode<CharT, BucketT>*
random_sample(unsigned char** strings, size_t n)
{
	const size_t sample_size = n/8192;
	debug()<<__PRETTY_FUNCTION__<<" sampling "<<sample_size<<" strings\n";
	size_t max_nodes = (sizeof(CharT) == 1) ? 5000 : 2000;
	TrieNode<CharT, BucketT>* root = new TrieNode<CharT, BucketT>;
	for (size_t i=0; i < sample_size; ++i) {
		unsigned char* str = strings[size_t(drand48()*n)];
		size_t depth = 0;
		TrieNode<CharT, BucketT>* node = root;
		while (true) {
			CharT c = get_char<CharT>(str, depth);
			if (is_end(c)) break;
			depth += sizeof(CharT);
			node->extend(c+1);
			if (not node->is_trie(c)) {
				node->_buckets[c] = new TrieNode<CharT, BucketT>;
				make_trie(node->_buckets[c]);
				if (--max_nodes==0) goto finish;
			}
			node = node->get_node(c);
			assert(node);
		}
	}
finish:
	return root;
}
开发者ID:Komalesh,项目名称:string-sorting,代码行数:28,代码来源:burstsort2.cpp


示例11: pseudo_sample

static TrieNode<CharT, BucketT>*
pseudo_sample(unsigned char** strings, size_t n)
{
	debug()<<__func__<<"(): sampling "<<n/8192<<" strings ...\n";
	size_t max_nodes = (sizeof(CharT) == 1) ? 5000 : 2000;
	TrieNode<CharT, BucketT>* root = new TrieNode<CharT, BucketT>;
	for (size_t i=0; i < n; i += 8192) {
		unsigned char* str = strings[i];
		size_t depth = 0;
		TrieNode<CharT, BucketT>* node = root;
		while (true) {
			CharT c = get_char<CharT>(str, depth);
			if (is_end(c)) break;
			depth += sizeof(CharT);
			node->extend(c+1);
			if (not node->is_trie(c)) {
				node->_buckets[c] = new TrieNode<CharT, BucketT>;
				make_trie(node->_buckets[c]);
				if (--max_nodes==0) goto finish;
			}
			node = node->get_node(c);
			assert(node);
		}
	}
finish:
	return root;
}
开发者ID:Komalesh,项目名称:string-sorting,代码行数:27,代码来源:burstsort2.cpp


示例12: insert

	// Inserts a word into the trie.
	void insert(string s) 
	{
		if (s.empty())
			return;

		TrieNode* p = root;

		int i = 0;
		while (i < s.size())
		{
			TrieNode* tmp = p->findCh(s[i]);
			if (nullptr == tmp)
			{
				p->addChild(s[i]);
				++i;
				p = p->getLastChild();
			}
			else
			{
				++i;
				p = tmp;
			}
		}

		p->isAWord(true);

		return;
	}
开发者ID:congnima,项目名称:Leetcode,代码行数:29,代码来源:ImplementTrie(Prefix+Tree).hpp


示例13: insert

void Trie::insert(string s) {
    TrieNode* curr = root;
    for(int i=0; i<s.length(); i++){
        if(curr->inChildren(s[i])) curr = curr->getChild(s[i]);
        else curr=curr->addChild(s[i]);
    }
    curr->addChild('#');
}
开发者ID:fengyu225,项目名称:lintcode,代码行数:8,代码来源:lib.cpp


示例14: naiveTest

void naiveTest() {
	TrieNode* trie = new TrieNode();
	trie->insert("HELLO",1);
	assert(1 == trie->find("HELLO")->terminal);
	assert(NULL == trie->find("HELLOB"));
	assert(-1 == trie->find("HELL")->terminal);
	delete trie;
}
开发者ID:MJ111,项目名称:algorithm-snippet,代码行数:8,代码来源:aho-corasick.cpp


示例15: startsWith

 // Returns if there is any word in the trie
 // that starts with the given prefix.
 bool startsWith(string prefix) {
     TrieNode* node = root;
     for(auto c:prefix) {
         node = node->subNode(c);
         if(node == nullptr) return false;
     }
     return true;
 }
开发者ID:wangqifei,项目名称:leetcode,代码行数:10,代码来源:208_ImplementTrie.cpp


示例16: startsWith

// Returns if there is any word in the trie
// that starts with the given prefix.
bool Trie::startsWith(string prefix) {
    TrieNode* curr = root;
    for(int i=0; i<prefix.length(); i++){
        if(!curr->inChildren(prefix[i])) return false;
        curr = curr->getChild(prefix[i]);
    }
    return true;
}
开发者ID:fengyu225,项目名称:lintcode,代码行数:10,代码来源:lib.cpp


示例17: search

// Returns if the word is in the trie.
bool Trie::search(string key) {
    TrieNode* curr = root;
    for(int i=0; i<key.length(); i++){
        if(!curr->inChildren(key[i])) return false;
        curr = curr->getChild(key[i]);
    }
    return curr->inChildren('#');
}
开发者ID:fengyu225,项目名称:lintcode,代码行数:9,代码来源:lib.cpp


示例18: search

 // Returns if the word is in the trie.
 bool search(string word) {
     TrieNode* node = root;
     for(auto c:word) {
         node = node->subNode(c);
         if(node == nullptr) return false;
     }
     return node->isend;
 }
开发者ID:wangqifei,项目名称:leetcode,代码行数:9,代码来源:208_ImplementTrie.cpp


示例19: search

 // Returns if the word is in the trie.
 bool search(string key) {
     TrieNode *cur = root;
     for(auto ch : key) {
         cur = cur->get_child(ch);
         if (cur == nullptr)
             return false;
     }
     return cur->is_end;
 }
开发者ID:sarahHe,项目名称:LeetCode-solution,代码行数:10,代码来源:Implement+Trie+(Prefix+Tree)+.cpp


示例20: startsWith

 // Returns if there is any word in the trie
 // that starts with the given prefix.
 bool startsWith(string prefix) {
     TrieNode *cur = root, *tmp;
     for (auto c: prefix) {
         if ((tmp = cur->find(c)) == NULL)
             return false;
         cur = tmp;
     }
     return true;
 }
开发者ID:mkfsn,项目名称:LeetCode,代码行数:11,代码来源:implement-trie-prefix-tree.cpp



注:本文中的TrieNode类示例由纯净天空整理自Github/MSDocs等源码及文档管理平台,相关代码片段筛选自各路编程大神贡献的开源项目,源码版权归原作者所有,传播和使用请参考对应项目的License;未经允许,请勿转载。


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C++ Trigger类代码示例发布时间:2022-05-31
下一篇:
C++ Trie类代码示例发布时间:2022-05-31
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap