Distinct Substrings

struct Trie{
char c;
vector<Trie*> children;
Trie(char c): c(c) {
children.assign(26, nullptr);
}
};
int solve(string s) {
if (s.empty())return 0;
const int n = s.length();
Trie* root = new Trie('#');
Trie* curr = root;
int ret = 0;
for (int i = 0; i < n; ++i){
curr = root;
for (int j = i; j < n; ++j){
Trie* child = curr -> children[s[j] - 'a'];
if (child == nullptr){
ret++;
Trie* newTrie = new Trie(s[j]);
curr -> children[s[j] - 'a'] = newTrie;
}
curr = curr -> children[s[j] - 'a'];
}
}
return ret;
}

For this specified problem, we don’t need to record the character for each Trie node as the children’s index can already tell us the character information.

struct Trie{
vector<Trie*> children;
Trie(){
children.assign(26, nullptr);
}
};
int solve(string s) {
if (s.empty())return 0;
const int n = s.length();
Trie* root = new Trie();
Trie* curr = root;
int ret = 0;
for (int i = 0; i < n; ++i){
curr = root;
for (int j = i; j < n; ++j){
Trie* child = curr -> children[s[j] - 'a'];
if (child == nullptr){
ret++;
Trie* newTrie = new Trie();
curr -> children[s[j] - 'a'] = newTrie;
}
curr = curr -> children[s[j] - 'a'];
}
}
return ret;
}

Data Scientist/MLE/SWE @takemobi