Trie
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
#include <iostream>
#include <map>
#include <regex>
#include <string>
using namespace std;
struct Node {
map<char, Node*> children;
bool terminal;
};
bool isTokenDelimiter(char c) {
return c < 'a' || c > 'z';
}
bool isWordDelimiter(char c) {
return isTokenDelimiter(c) && (c < 'A' || c > 'Z') && (c < '-' || c > ':') && c != '_';
}
void insertToken(Node *root, string token) {
cout << "insert token: " << token << endl;
for (int i = 0; i < token.length(); ++i) {
if (root->children.find(token[i]) == root->children.end()) {
root->children.emplace(token[i], new Node());
}
root = root->children[token[i]];
}
root->terminal = true;
}
void insertWord(Node *root, string word) {
cout << "insert word: " << word << endl;
for (int i = 0; i < word.length(); ++i) {
if (isTokenDelimiter(word[i])) {
insertToken(root, word.substr(i));
}
}
insertToken(root, word);
}
int countTokens(Node *root) {
int count = root->terminal ? 1 : 0;
for (auto it : root->children) {
count += countTokens(it.second);
}
return count;
}
int main() {
Node *root = new Node();
string word;
char c;
while (cin.get(c)) {
if (isWordDelimiter(c)) {
insertWord(root, word);
word.clear();
} else {
word += c;
}
}
cout << countTokens(root);
return 0;
}
Cpp
INFO