Trie Algorithm
The Trie Algorithm, also known as the Prefix Tree or Digital Tree, is an efficient data structure used for organizing a collection of strings or sequences into a tree-like structure. The primary purpose of a trie is to enable fast retrieval of strings that share a common prefix. This algorithm is widely used in applications such as autocomplete features, spell-checkers, IP routing, and many other search-related tasks.
The trie algorithm constructs a tree where each node represents a single character of a string or sequence. The root node is an empty node, while the child nodes represent the first characters of the strings. Each subsequent level of the tree holds the next character in the strings. When searching for a string in the trie, one can simply traverse the tree from the root node, following the child nodes that match the characters of the string. If the traversal reaches a leaf node, the string is found in the trie. This structure allows for efficient string queries and insertions, making it a highly useful algorithm in computer science and information retrieval systems.
/****************************************************************************
Trie. Builds tree from the set of strings. O(total length of strings)
This code counts number of different substrings in the string.
Based on problem B from here: http://codeforces.ru/gym/100133
****************************************************************************/
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
using namespace std;
const int ALPH = 26;
const int MAXN = 100500;
struct node {
int go[ALPH];
};
string s;
node trie[MAXN];
int node_num;
int main() {
assert(freopen("unequal.in","r",stdin));
assert(freopen("unequal.out","w",stdout));
getline(cin, s);
for (int i = 0; i < (int) s.length(); i++) {
int cur = 0;
for (int j = i; j < (int) s.length(); j++) {
int ch = s[j] - 'a';
if (trie[cur].go[ch] == 0) {
node_num++;
trie[cur].go[ch] = node_num;
}
cur = trie[cur].go[ch];
}
}
printf("%d\n", node_num);
return 0;
}
