Skip to content

Instantly share code, notes, and snippets.

@ar1a
Last active May 15, 2016 03:47
Show Gist options
  • Save ar1a/cfdf655afd5695fbf12ba780b5908f5b to your computer and use it in GitHub Desktop.
Save ar1a/cfdf655afd5695fbf12ba780b5908f5b to your computer and use it in GitHub Desktop.
C++ Trie implementation including ready-to-go autocomplete
word
word2
word3
word4
#include <iostream>
#include "trie.h"
int main()
{
Trie trie;
trie.insert("word");
trie.insert("word2");
trie.insert("word3");
trie.insert("word4");
trie.insert("fugg");
auto&& ac = trie.autocomplete("wo");
for (auto&& str : ac) {
printf("%s\n", str.c_str());
}
return 0;
}
#ifndef __TRIE_HPP
#define __TRIE_HPP
#include <map>
#include <string>
#include <vector>
class trie_node
{
public:
trie_node(const std::string& val = "") : value(val), is_end(false) {}
bool is_end;
std::string value;
std::map<char, trie_node> child;
void add(char c)
{
if (value == "")
child[c] = trie_node(std::string(1, c));
else
child[c] = trie_node(value + c);
}
std::vector<std::string> all_prefixes()
{
std::vector<std::string> ret;
if (is_end) ret.push_back(value);
if (!child.empty()) {
for (auto&& tuple : child) {
auto&& nodes = tuple.second.all_prefixes();
ret.insert(ret.end(), nodes.begin(), nodes.end());
}
}
return ret;
}
};
/*
* based off https://github.com/vivekn/autocomplete/blob/master/trie.h
*/
class Trie
{
public:
Trie() : head() {}
std::string find(const std::string& word)
{
trie_node* node = &head;
for (auto&& ch : word) {
if (node->child.find(ch) == node->child.end()) return "";
node = &node->child[ch];
}
return node->value;
}
void insert(const std::string& word)
{
trie_node* node = &head;
for (auto&& ch : word) {
if (node->child.find(ch) == node->child.end()) node->add(ch);
node = &node->child[ch];
}
node->is_end = true;
}
std::vector<std::string> autocomplete(const std::string& prefix)
{
trie_node* node = &head;
for (auto&& ch : prefix) {
if (node->child.find(ch) == node->child.end()) return std::move(std::vector<std::string>());
node = &node->child[ch];
}
return node->all_prefixes();
}
private:
trie_node head;
};
#endif
@ar1a
Copy link
Author

ar1a commented Apr 15, 2016

for some reason it insists that output.txt is the filename when it really isn't

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment