Sponsored
Sponsored
This approach utilizes a reversed Trie (prefix tree) to efficiently manage and query suffixes of input characters. By storing the reversed words in a Trie, we can match suffixes of the input stream by querying from the current character backwards. For each character queried, we move through the Trie from those characters up to a certain limit (or until no further match) to see if any of the suffixes match one of the stored words.
Time Complexity for insertion: O(N*L), where N is the number of words and L is the maximum length of a word.
Time Complexity for queries: O(Q*L) where Q is the number of queries and L is the maximum length of a word.
Space Complexity: O(N*L) for storing the words in the Trie.
1class TrieNode:
2 def __init__(self):
3 self.children = {}
4 self.is_end_of_word = False
5
6class StreamChecker:
7 def __init__(self, words):
8 self.root = TrieNode()
9 self.stream = []
10 for word in words:
11 node = self.root
12 for char in reversed(word):
13 if char not in node.children:
14 node.children[char] = TrieNode()
15 node = node.children[char]
16 node.is_end_of_word = True
17
18 def query(self, letter):
19 self.stream.append(letter)
20 node = self.root
21 for char in reversed(self.stream):
22 if node.is_end_of_word:
23 return True
24 if char not in node.children:
25 return False
26 node = node.children[char]
27 return node.is_end_of_wordThe implementation involves creating a Trie that stores each word in reverse. When a query is made, characters are added to a list representing the current stream. We then check from the current end of the stream backwards through the Trie to determine if any suffix matches a word.
The Aho-Corasick algorithm is useful for searching multiple 'dictionary' words within a text. We build an automaton with all words and query the stream letters. This data structure enables matching of all dictionary words in parallel through a finite state machine that jumps quickly between states even upon mismatches.
Time Complexity for building: O(N*L), because we insert and construct failure links.
Time Complexity for queries: O(Q*L) leveraging finite state machine transitions.
Space Complexity: O(N*L) due to the state-space storage representing words.
1#include <vector>
2#include <queue>
3#include <unordered_map>
4using namespace std;
5
class AhoCorasick {
public:
struct TrieNode {
unordered_map<char, TrieNode*> children;
TrieNode* fail = nullptr;
bool is_end = false;
};
TrieNode *root = new TrieNode();
void insert(const string &word) {
TrieNode *node = root;
for(char c : word) {
if(!node->children.count(c)) {
node->children[c] = new TrieNode();
}
node = node->children[c];
}
node->is_end = true;
}
void build() {
queue<TrieNode*> q;
root->fail = root;
for(auto &p : root->children) {
p.second->fail = root;
q.push(p.second);
}
while(!q.empty()) {
TrieNode *curr = q.front(); q.pop();
for(auto &p : curr->children) {
char c = p.first;
TrieNode *child = p.second;
TrieNode *fail = curr->fail;
while(fail != root && !fail->children.count(c)) {
fail = fail->fail;
}
if(fail->children.count(c)) {
child->fail = fail->children[c];
} else {
child->fail = root;
}
child->is_end |= child->fail->is_end;
q.push(child);
}
}
}
};
class StreamChecker {
AhoCorasick ac;
AhoCorasick::TrieNode* node;
public:
StreamChecker(vector<string>& words) {
for(const string &word : words) {
ac.insert(word);
}
ac.build();
node = ac.root;
}
bool query(char letter) {
while(node != ac.root && !node->children.count(letter)) {
node = node->fail;
}
if(node->children.count(letter)) {
node = node->children[letter];
}
return node->is_end;
}
};This C++ solution implements the Aho-Corasick algorithm: