Trie & KMP
KMP Algorithm
What’s the function of KMP?
When we have a text and a string, we want to know whether the string is in it or not, if it is in the text, how many times it appeared? If we use the naive algorithm, it will consume $O(n \cdot m)$(m is the length of the passage and the n is the length of the string) because we should compare one by one. But if the string and the text have some rules, for example, text = abcadabcab, the string is abcab. In this case, apparently we have better method to solve it. The algorithm is KMP, which full name is Knuth–Morris–Pratt Algorithm. And we define the string we need to find in the text as pattern.
The logic of KMP and proff
We need two pointers: the pattern pointers and the text pointers to compare.
When we encounter a mismatch, it means that the characters we compared previously must be equal. We can check the LPS length of the previous character. If this length is greater than 0, it means that the pattern ending with the previous character has equal prefix and suffix. We can simply move the prefix to the suffix position and compare the first character after the prefix with the character currently pointed to by the text pointer. If they are not equal, we repeat this process until they are equal or fall back to the first character. If the first character is also not equal, we simply move the text pointer and compare again. This way, you don’t have to move characters one by one, which significantly improves the matching speed.
Is it always right? Proof:
When text[i] not equal to pattern[j]
Knowing lps[j - 1] = t, t <= j - 1 => pattern[0 ~ t-1] = pattern[j - t ~ j - 1]
and text[i - j ~ i - 1] = pattern[0 ~ j - 1] => text[i - t ~ i - 1] = pattern[j - t ~ j - 1]
=> text[i - t ~ i - 1] = pattern[0 ~ t-1]
That means existing the prefix of pattern which equals to text[i - t ~ i - 1]
We don’t need to compare from the beginning!
So the C++ code is:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void KMPsearch(string& text, string& pattern)
{
int n = text.size();
int m = pattern.size();
vector<int>lps = LPSlength(pattern);
int i = 0, j = 0;
while(i < n)
{
if(text[i] == pattern[j])
{
i++; j++;
}
if(j == m) j = lps[j - 1]; // if we want to know how many times the pattern appeared, we can add a count to contain it.
else if(i != n && text[i] != pattern[j])
{
if(j != 0) j = lps[j - 1];// fall back
else i++;
}
}
}
LPS, How to get LPS length
Using the example I have mentioned above, when the prefix abca of the string abcab have been compared, b is not equal to d. In that moment, we can actually move the first a of the string to the second a of the text, instead of just moving a to align b, which is the second letter of the text. Repeat this process. Moving like this we can speed up the matching process obviously. But that’s a question: What can we do to move like this? Introducing a concept: LPS(Longest prefix which is also suffix), it means we should find the length of the longest proper prefix which is also a suffix. A proper prefix is a prefix that doesn’t include whole string. In a text, for example: ababc, we need to know the LPS length ending at each character. For a, it is single character, and we defined its LPS length is 0. For ab, the LPS length is 0 because the prefix not equal to suffix. For aba, the prefix a equal to the suffix so the LPS length is 1. For abab, the prefix is ab, the suffix is ab, so the length of LPS is 2. For ababc, its LPS length is 0. We should record the LPS length of each character in an array [0, 0, 1, 2, 0]. The index is equal to the index of the string.
Knowing what the LPS length is, how can we get it? We will use a leading pointer and a trailing pointer. If equal, move forward both; If not equal, the trailing one fall back and compare again. If still not equal, move the leading one only. So the key to get the LPS length is the fall back logic. We need to borrow the logic of KMP fall back pattern pointer, meaning that we consider the first character to the leading pointer as the text and the first character to the trailing pointer as the pattern. The fall back logic is same as move the prefix to the suffix position and compare the first character after the prefix with the character currently pointed to by the text pointer. Just replace the move prefix with move trailing pointer. And don’t forget to record the LPS length of each character!
Achieve in the c++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> LPSlength(string& pattern)
{
int m = pattern.size();
vector<int>lps(m, 0);
int len = 0;
for(int i = 1; i < m;)
{
if(pattern[i] == pattern[len])
{
lps[i++] = ++len;
}
else
{
if(len != 0) len = lps[len - 1];
else lps[i++] = 0;
}
}
}
Time complexity
Because the logic of KMP searching and LPS length computing is same, so we just analyze one of them. So we analyze the KMP search: the text pointer always move forward, so it will consume $O(n)$ (n is the length of the text). Even the worst situation, the times of pattern pointer move back is linear too, and it won’t beyond n times. So the KMP search is $O(n)$, equal to the text length. So the LPS length computing is $O(m)$, equal to the pattern length. Above all, the time complexity of KMP is $O(n + m)$, better than $O(nm)$.
Trie
what is Trie
A Trie is a tree-like structure that stores strings by their prefixes. For example, I want to store the words: “cat”, “cap”, “dog”. It the Trie will be like:
In this way we can did many operations such as insert, search and so on. By the way, if we insert cat, we can set whether the c or ca can be finded or not.
So we can use code to translate this graph:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct TrieNode{
TrieNode* children[1000];// maybe it will contain many characters instead of only the 26 letters
bool isEndOfWord;
TrieNode(){
isEndOfWord = false;
for(int i = 0; i < 1000; ++i) children[i] = nullptr;
}
};
class Trie{
private:
TrieNode* root;
public:
Trie(){
root = new TrieNode();
}
};
This is the Trie. We will add some functions to push it to work.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void insert(string& s){
TrieNode* node = root;
for(auto c : s)
{
int i = c - 'a';
if(!node -> children[i]) node -> children[i] = new TrieNode();
node = node -> children[i];
}
node -> isEndOfWord = true;
}
void search(string& s){
TrieNode* node = root;
for(auto c : s)
{
int i = c - 'a';
if(!node -> children[i]) return false;
node = node -> children[i];
}
return node -> isEndOfWord;
}
There are too many operations that Trie can do. And most of them can be expended based on these two basic functions.
Failure link
From the KMP, when the string mismatched, then it will be back based on the next array but not be back to the start, because of the “link” we set. We define this link as “failure link”.
Aho-Corasick automaton
We insert some pattern in the Trie. Giving a text, we want to know how many patterns we have inserted in the Trie are included in the text. Just same as the KMP search, if it needs return to the root always, the time will be waste a lot. So we need to set some failure links which is similar to the KMP to save time.
Above all, the Aho-Corasick automaton is the trie tree with the fail link. In this case, we just solve two question: How to implement the failure link in Trie?
The logic of setting failure link
From the KMP, we know the failure link is a function that pull the prefix to the position of suffix. In the Trie, we initially introduced the “state”. If we insert the “his” to the Trie, it will look like this: h -> i -> s. When the ‘h’ was inserted, we call the current state is ‘h’. When the ‘i’ was inserted, we call the current state is “hi”. When the ’s’ was inserted, we call the current state is “his”. If the current state is “his”, we call the “is” and ’s’ is the suffix of the state and call the ‘is’ is the longest suffix of the state. For the text, we will match from the beginning, so we need to take the prefix. Inputting a text, when the text mismatch with the current state, the previous state is matched, which means that the prefix of the text match with the suffix of the previous state. So the prefix has matched, we just move the text to the next state whose prefix match with the suffix of last state. The failure link will do this work.
Above all, a failure link connects the suffix of one state to a state whose prefix is identical to that suffix, with the connection point located at the end of the suffix and the end of the prefix.
For example 
Implement in c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
struct TrieNode{
TrieNode* children[26];
TrieNode* fail;
bool isEndOfWord;
TrieNode(){
for(int i = 0; i < 26; ++i)
{
children[i] = nullptr;
}
isEndOfWord = false;
fail = nullptr;
}
}
class Trie{
private:
TrieNode* root;
public:
Trie(){
root = new TrieNode();
}
void insert(string& s)
{
TrieNode* node = root;
for(char ch : s)
{
int i = ch - 'a'; // attention here! the c equal to the order in the letter chart;
if(!node -> children[i]) node -> children[i] = new TrieNode();
node = node -> children[i];
}
node -> isEndOfWord = true;
}
void buildFL()
{
root -> fail = root;
queue<TrieNode*> q;
//Initialize the direct child of the root
for(int i = 0; i < 26; ++i)
{
if(root -> children[i])
{
root -> children[i] -> fail = root;
q.push(root -> children[i]);
}
}
// Using BFS
while(!q.empty())
{
TrieNode* cur = q.front(); q.pop();
for(int i = 0; i < 26; ++i)
{
TrieNode* child = cur -> children[i];
if(!child) continue; // no child, no fail;
// find the node which is root or with the child which has same id with cur -> children, the id is the order of the letter chart.
TrieNode* f = cur -> fail;
while(f != root && !f -> children[i])
f = f -> fail;
// if f = root, the child link the root; if f != root, child will link the child of f whose id is same as it only.
if(f -> children[i] && f -> children[i] != child)
f = f -> children[i];
// set the failure link.
child -> fail = f;
q.push(child);
}
}
}
int query(string& text)
{
TrieNode* cur = root;
int count = 0;
for(char ch : text)
{
int c = ch - 'a';
while(cur != root && !cur -> children[c]) cur = cur -> fail;
if(cur -> children[c]) cur = cur -> children[c];
TrieNode* temp = cur;
while(temp != root)
{
if(temp -> isEndOfWord) count++;
temp = temp -> fail;
}
}
return count;
}
}