Hello, my name is π three diamonds from Tech Galaxy.
You might think that KMP is a strange name, because KMP is not the beginning of three English words, but the names of three computer scientists. The three computer scientists who invented the algorithm were Knuth, Morris and Pratt. The first one is Donald Ervin Knuth (Gartner), the author of The Art of Computer Design and a very famous old expert in programming. M and P were also famous computer experts at that time, and the KMP matching algorithm was researched by the three of them together.
What is the KMP algorithm?
Quickly find the desired substring from the main string — the main string is the source string, and the substring to be found is the pattern string.
If we forget about KMP, let’s use the simplest algorithm, the brute-Force (BF), which we use a lot in algorithms, which has a name for it historically, which is our violent solution.
So how do we use brute force to match our strings? Here we need to compare the characters in our pattern string one by one at the beginning of a string of characters. If we can find a continuous string of characters that exactly match the characters in our whole pattern string, then we can consider that there are characters in this string that are consistent with the characters in our pattern string. The time of this algorithm is m times n. The length of m is the length of the original string, and n is the length of the pattern string.
Such a very high time complexity algorithm must have a serious impact on the performance of our program. So our computer scientists have done some research and found that with some algorithmic tricks, we can reduce the time complexity to O(m + n). This is the KMP algorithm invented by three scientists.
Let’s take a look at how the KMP matching algorithm actually works.
KMP algorithm matching process
Let’s start with a simple example. Suppose we now have two strings:
- Source: ABABABABABAAABABAA
- Pattern: AAAB
The ultimate goal of KMP algorithm is to find the substring matching our pattern string in our main string. Take a look at the following dynamic effects:
The red part inside is our main string, and our blue part is our pattern string. We quickly found the AAAB substring in the main string, and it matched our pattern string exactly. The most important point here is “fast”, and the KMP algorithm is designed to be able to quickly find our substrings in the main string.
Let’s first understand how to do the “unhappy” way, in fact, brute force cracking is generally more intuitive, but also easier to think of.
It’s not too hard to imagine that we would brute force all the letters in the main and pattern strings to compare and match one by one. If there is a mismatch, let the pattern string go back to the place next to the initial letter and start matching one by one again. And so on, eventually we either find a substring that matches, or we end up with no string in the main string that matches the pattern string.
Ok, let’s take a look at the effect:
It’s a pretty intuitive algorithm, right? One thing to note here is that in the first round of matching, when we encounter a character that doesn’t match, our Pointers I and j move to the second position in the main string. This action is called comparison pointer backtracking, and “backtracking” is the main reason why this simple algorithm is inefficient.
So what can we do to achieve what we call “fast” search?
Definitely using our KMP algorithm. The KMP algorithm can only move the pattern string backward, comparing the pointer without backtracking! Does that sound awesome? So let’s see how it works.
Let’s go back to where we just found a character that doesn’t match:
Here our pattern string is at position A, and our main string is at position B, which is obviously A mismatch. If we take a closer look at the first five letters, we notice two important things:
- This part of the main string matches the pattern string. Both are
ABBAB - The pattern string has two substrings at the left and right ends
ABIt’s exactly the same. These two strings are what we call pattern stringsCommon prefix and suffix
So with these two points, we can use the techniques in the KMP algorithm, and this is the core of the KMP algorithm, and once we understand the whole algorithm, we can understand it. We move the pattern prefix AB directly to where the pattern suffix is.
This move ensures that the string before the character that our current pointer matches matches up and down. In other words, the way we move around ensures that the characters we reuse match. In our example, the AB in front of us matches in the main string and the pattern string. So why does this happen? It’s just that our common prefix and suffix match, and they still match when we move them around.
So if you’re serious, you might wonder, if we’re moving the pattern string to this position, are we missing some other matches? I can safely say that between the two positions before and after the move, there is no successful match.
To be skeptical is the basic quality of a programmer. So let’s take a look at each one.
From the renderings above, we can see that moving from the beginning to the end does not match until we reach the position of the common suffix in our pattern string. This also proves the result we said above.
This is a special case, so let’s see what happens in general. In our special case, we found that when we reached the position of the failed character during the matching process, all characters up to that position in the pattern string matched the main string. Then we look for the common prefix and suffix in the matching string, which means we really only need to analyze the pattern string, because the string we analyze is exactly the same as the main string.
For a more general example, let’s say we now have a string of characters AB… . ABX … . It’s… Stands for multiple arbitrary characters, and X is the character that follows the common suffix AB. X can also be understood as the position where the first match between the pattern string and the main string fails.
All we have to do is move the common prefix to the same place as the common suffix, and then we can continue to match, which is what we just did in the example, and we have also proved that there is no match between the prefix and the suffix. So if there is, prove that the common suffix we chose is not the longest common suffix.
What does that mean? There are longer prefixes and suffixes in the characters before the location of the failed match. Here we have the concept of the longest common prefix and suffix.
The longest common prefix is — when there are multiple common suffixes in the string we are analyzing, we take the longest common prefix.
Now that we have covered the concept of the KMP algorithm, let’s go through the matching process of the above example. Let’s look at an animation to see the rest of the matching process
In the animation above, we start with the second matching position:
- Because by the logic above we already have the common prefix
ABMoved to the suffix position, so we can continue to match character by character - Matches to the main string
BAnd pattern stringAThe match failed again - At this point we’re going to look at the pattern string
AThe character that has already been matchedABBABAThere are only prefixes and suffixes in this stringA - So finally we make the pattern string from the prefix
AMove to suffixAThe location of the - At this point we find that our pattern string has exceeded the length of the main string, so there is no substring in the main string that can match the pattern string.
Obviously this matching method, compared with our “violent solution” method of comparison times much less, naturally our algorithm will be much more efficient.
Let’s look at another example:
- The main series:
ABABABAABABAAABABAA - Pattern string:
ABABAAABABAA
First we align the two strings in the left header, then we start comparing the letters in the main and pattern strings one by one.
By the sixth letter, we found a mismatch. At this point we start analyzing the string ABABA that we matched earlier. Here we need to find the longest common suffix, and the best way to find the longest common suffix is to extend from both ends inward.
In our animation above, we can see how we find the longest prefix and suffix. In the process we found 3 pairs of antecedents and suffixes:
- A and A
- ABA and ABA
- ABABA and ABABA
All three pairs of prefixes match perfectly, but the third pair is an invalid prefix because it is the same length as our string. That means we don’t have to move at all, we can move from the prefix to the suffix. That doesn’t make any sense for us to move on to the next match. So only the first and second suffixes are valid.
From the example above, we can put a constraint on finding the common prefix: we need to find the longest common prefix that is less than the length of the left terminal string at the wrong position.
Since we need the longest common prefix and suffix, the second group of ABA is the most suitable.
Once we have found the longest common prefix, we can move the pattern string from the prefix to the suffix, and then continue matching characters.
Scanning one by one, we found another mismatch at the seventh letter of the pattern string, which is ABABAA to the right. Through god’s perspective, we can see that there are only two common suffixes in this substring, which are A and A.
As before, move the position of the common prefix to the position of the common suffix, and then continue matching. At the end of the match we find a substring in the main string that is exactly the same as the pattern string. The result of this is that we have the desired string in our main string (that is, our pattern string).
Normally our strings are stored in an array of characters, and arrays cannot be moved in memory. So all of the examples that we’ve just shown you are just visualization, and we need to translate them into something that’s computer friendly.
KMP next array
Now that we know we can’t move arrays in real code, we need to translate this concept into logic that our code can execute.
The first thing we need to understand is that in our algorithm matching, we know that all we’re moving is our pattern string and our main string is not changing at all. Therefore, in the matching of KMP algorithm, the most critical operations and changes are in our pattern string.
In other words, we just need to study the pattern string and mine it for information, and then we can use it to match any string.
Let’s start with an example to see how we need to explore a pattern string and mine its information.
So let’s just use our previous example ABABAAABABAA.
First we’ll subscript the string to make it easier to analyze:
Note: here we are storing the data at subscript 0, whereas many schools teach KMP algorithms to store data at subscript 1, but in code, most data structures start at subscript 0. If we use the data at 1, it will be confusing when writing code. In my opinion, this is one of the reasons why the KMP algorithm, which is relatively simple, becomes difficult to understand. Some tutorials start from 0, some tutorials start from 1, and then when writing code the array starts from the index 0. We end up with headaches and hair loss.
But even if we were to start at subscript 1, our matching string and pattern string would both have to start at subscript 1, otherwise our next array would be messed up. ** For the sake of better understanding and closer to the original data structure in the code, we will all start with the subscript 0. **
Ok, so let’s start analyzing this pattern string.
First we assume that this pattern string can be matched with any main string using the KMP algorithm. The position of each character in the pattern string could be mismatched.
But what we want to look at is the length of the common prefix and suffix of the preceding string if a mismatch occurs at any of the positions, so that we can get the position we need to move the pattern string back.
The subscript 0location
First of all, we do not need to calculate the value of next at the position of the subscript 0 of the pattern string, because the character length of this position is 1, which cannot obtain a longest common suffix, because the length of the longest common suffix must be less than the length of the substring itself
So the first character’s next value must be 0.
The subscript 1location
Now let’s look back and see if the character after the position 1 in the pattern string fails to match.
- The characters from subscript 0 to the current subscript are
ab - There is obviously no common prefix or suffix
- So the longest common prefix and suffix is
0
So the Next value at subscript 1 is 0.
The subscript 2location
Now let’s look at what happens when a match fails after the subscript 2 position.
- The characters from subscript 0 to the current subscript are
aba - And here we see
aIs the common prefix and suffix of the segment character - And the length of this prefix and suffix is
1
So the Next value at subscript 2 is 1.
The subscript 3location
- The characters from subscript 0 to the current subscript are
abab - The common prefix and suffix here are
ab - Its length is 1, 2, 3
2
So the Next value at subscript 3 is 2.
The subscript 4location
- The characters from subscript 0 to the current subscript are
ababa - The common prefix and suffix are
aba - Its length is 1
3
So the Next value at subscript 4 is 3.
The subscript 5location
- The characters from subscript 0 to the current subscript are
ababaa - The common prefix and suffix are
a - Its length is 1
1
So the Next value at subscript 5 is 1.
N bit matching rule
Here we analyze the Next values of five subscripts, and we can obviously find a pattern. The Next value at each position is essentially the length of the common prefix and suffix in the characters from the beginning of the string to the current position.
So let’s write down the rest of the Next values.
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| String | a | b | a | b | a | a | a | b | a | b | a | a |
| Next | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 | 6 |
This is the Next array we often hear about in KMP algorithms.
In many places this is also called a prefix array or PMT array. Because its corresponding value represents the common length of the prefix and suffix in the preceding string. But what the Next array needs to do in the code is “move the prefix to the suffix.”
To do this, we need to know the subscript position of the last character of our prefix in each position. Curiously, each array in our current Next array is preceded by the subscript of the position of the last character of our prefix.
So we just need to move all the values of the current Next array to the right to get the Next array we really want.
With this Next array we can use the information provided by this array to find the Next matching position in the event of a mismatch at any position in our pattern string.
And then we see that 0 is empty, there’s no value. So we usually assign -1 to the zero position.
We end up with data like this:
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| String | a | b | a | b | a | a | a | b | a | b | a | a |
| Prefix/PMT | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 | 6 |
| Next | – 1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 |
The code examples
Let’s take a look at how KMP code should be written. First of all, KMP must be a function and will receive two parameters, one is source and the other is pattern, representing the main string and pattern string respectively.
Then our processing will be divided into two parts, the first part is calculating the Next array, and the second part is matching.
Compute the Next array
According to the reasoning logic of our KMP algorithm above, to calculate the Next array for matching, we first need to find the longest common prefix and suffix of the character that precedes each position. And that data is the prefix array.
When looking for a prefix or suffix, it’s easier to see the longest common prefix or suffix in a paragraph if we use the “God perspective: Our smart brain” analysis. But for a computer, it takes a little bit of a clunky way to go from one to the other, and it’s really not that easy to write in code. So what to do?
Just like when we solve algorithm problems, when we encounter a complex problem, we try to find simple rules in the complex problem. Thus, we can achieve the effect of weft drop on this topic, that is, the effect of “simplification of complex problems”.
Let’s take ababaaababaa as an example. First, we can separate the character before each matching character and list its common prefix and suffix. Then we can see if there is any pattern:
- Ab: 0
aba: 1.abab: 2ababa: 3 (aba, aba)ababaa: 1.ababaaa: 1.ababaaab: 2ababaaaba: 3ababaaabab4:ababaaababa: 5
What patterns can we find here? There is. Let’s take the aba and abab strings. First, we know that the common suffix of ABA is a, and the common suffix is 1 in length. Suppose we wanted the longest common prefix to be 2, we could simply add a B to the end of ABA.
So another way to think about it, is it based on ABA, we just need to determine if the next character is a B to know what the longest common prefix or suffix of the next character is?
If the next character of ABA is b, the common suffix of the next character must be the current longest common suffix +1, which is 1+1=2. Ok, let’s make sure this rule is correct!
Let’s test this out with ababaaa, ababaaa whose longest common prefix is a, length 1, and it’s preceded by ab. According to our logic, if the next character of ababaaa is b, then the longest common prefix and suffix can become ab, which is of length 2.
Sure enough, the next character is b, and it really is of length 2. So now the character is ababaaab, common prefix ab, length 2. Perfect! We found our first pattern!
To summarize this rule, we compare the next character of our common prefix with the next character of our common suffix, and if they are the same, then the longest common suffix of our next character will be the longest common prefix + 1.
The logic is the same as in the following animation:
The j in this animation refers to the end character of our common prefix, and the I refers to the end character of our common suffix.
If you are careful, you will notice that the current longest common prefix and suffix + 1 can also be interpreted as the subscript + 1 of j. We’ll see that the rule is the same. (Why mention it here? Because this rule is easier to code.
What if the next character doesn’t match? Boy, that’s a good question! It doesn’t matter, our example also has this situation, let’s take them out to analyze, trust our powerful brain can always pick up some clues!
So let’s take ababa and Ababaa separately. First, ababa has a common prefix of aba of length 3, so if the next character in ababa is B, we have a common prefix of length 4. Unfortunately, we don’t get off easy. The next character is a. So here we have the exact opposite of the scenario we just described.
“———— ~ 2 hours later ~ ————-“
What to do? Can’t find the rule!!
Don’t get me wrong, I’m not very upset, but my scalp is numb, so I need to fix my hair. This is not the reason why programmers often lose their hair. Please don’t think too much about it
Well, since we can’t think of anything else, let’s put together a table of the longest common prefixes and suffixes for each position in the pattern string, and maybe we can figure it out.
| The subscript | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| character | a | b | a | b | a |
a |
a | b | a | b | a | a |
| prefix | 0 | 0 | 1 | 2 | 3 |
1 |
1 | 2 | 3 | 4 | 5 | 1 |
| pos | – | – | – | j |
– | i |
– | – | – | – | – | – |
In the table above, we mark the position of the last letter in two strings. We also mark the current position of j and I. Here we can see:
- ab
aThe common prefix for BA is ABA, so the last character of the prefix is inThe position of subscript 2 aThe common prefix of babaa is a, so the last character of the prefix is inThe position of subscript 0
Do you see anything, class? In fact, the difference between ababaa and ababa is this subscript, which means that if our j goes back to subscript 0, we have the same character that j and I refer to. Then if j goes back to 0, we can use the rule we just analyzed: j subscript + 1 = the length of the common prefix and suffix of the next string of characters.
So here we have the j pointer backtracking at zero subscript, and the longest common suffix of the next string is 0 + 1 = 1. Whoa! There you go! That’s right!
All we know here is that j needs to go back to the previous index, but after all, if we want to write this logic in code, there must be a “pattern”. If we look at the table above, we see that j points to our prefix value of 2, so can we replace the current j position with the prefix value of the current j subscript? So we can get the j to go back even further.
The first thing we need to know is that the value in our prefix table represents the length of the longest common prefix and suffix in the string from the beginning to the current position. The current prefix value for the j position is 2, and the corresponding common prefix is ab. If we use this value to move the j position, it will point to the third character A, the second A in ABA.
According to the first rule we just sorted out, we match the value I points to with a character after the current common prefix and suffix. So now if we move j to subscript 2, let’s see what the character before it is?
| The subscript | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| character | a |
b |
a | b | a | a | a | b | a | b | a | a |
| prefix | 0 | 0 | 1 |
2 | 3 | 1 |
1 | 2 | 3 | 4 | 5 | 1 |
| pos | – | – | j |
– | – | i |
– | – | – | – | – | – |
We can see that the string before j is ab. Obviously ab is not a common suffix in our current ababaa character. So that’s not the right way to move the j. So we need a different strategy.
Our goal is simply to get j back to the correct position. If the current corresponding prefix value does not work, then what about the prefix value of J-1?
The value of j-1 is actually the value of prefix corresponding to j in the table above, which is 1.
| The subscript | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| character | a |
b | a | b | a | a | a | b | a | b | a | a |
| prefix | 0 | 0 |
1 | 2 | 3 | 1 |
1 | 2 | 3 | 4 | 5 | 1 |
| pos | – | j |
– | – | – | i |
– | – | – | – | – | – |
At this point we see that the j position corresponds to the common prefix of the string. It shows that our method of j backtracking is correct, but we also find that the character corresponding to j position is not equal to the character corresponding to I now.
Now that the strategy of j backtracking is correct, we’re going to do the same thing with j backtracking again, moving it forward. And then j-1 is going to be 0.
At this point, the character that j points to is the same as the character that I points to. Using our previous rule, the longest common suffix of the string before the position I is 0 + 1 = 1.
We found that we got the right value. So with this rule in mind, we can calculate the data in the prefix table, which is the common length of the characters before each position. Then we can get our next array from the prefix table.
Let’s summarize these two rules:
iSo if I start at one subscript,jMatches characters corresponding to each other’s positions, starting with the 0 subscript. If the same, prove that the character before the current position of I has a common prefix and suffix of lengthJ subscript plus 1- if
iεjIf the corresponding character does not match, j will go back to the previous position to find a matching character, and the backtracking rule isprefix[j-1].
It is important to note here that if our j has been backtraced to subscript 0 and still does not find a common prefix, we need to stop backtracking j and prove that this string has no common prefix or suffix.
So with that said, the theory is clear, so let’s look at the code and see how we can implement it.
According to the above theoretical analysis, we first need to calculate the prefix array, and then move all the values of the prefix array to the right to obtain our Next array.
In generating the Next array we’ll use a Next variable to store the data. According to the above analysis of the Next Array, its length must be the same as our pattern string length, so when we create Array, we directly fill the table with data. So let’s just fill in the zeros here.
function kmp (source, pattern) {
// Compute the Next array
let next = new Array(pattern.length).fill(0);
// Find common prefixes in pattern strings
let i = 1,
j = 0;
}
Copy the codeAs we said before, subscript 0, we don’t need to analyze its next value, so our I can just start at subscript 1. Here I defaults to 1 and j defaults to 0.
Now we can start looping through our pattern string. Here we use a trick. In the theory above, we calculate the prefix data and then get our next array by moving all the values to the right one place.
But we can actually do that as we go through the loop. Every time we compare the values of I and j, if we find a match, we place the corresponding prefix value one bit below the current subscript. Next [j+1]. So we must have moved all prefix values one to the right. You don’t have to move it again.
Now that we have this technique, we can have fun writing code that generates the Next array
Here we apply the two rules we just analyzed to the two cases. In the first case, the character corresponding to I is the same as the character corresponding to j. In this case, we know that the prefix value is j + 1.
We know the prefix value, which we need to put in the next[j+1] position as per the above tip.
But, since we match I and j, we also need to move j and I to the next index. Because j moved by one, that’s the same thing as j itself already plus 1. Next [I] = j, and I doesn’t need to +1, because I already +1 when I moves to the next index.
And then there’s the second case, where the characters for I and j don’t match, and we’re going to have j backtrack. Because we have moved the prefix array one bit to the right, we can use j = next[j] instead of next[J-1].
And then finally, we said that if j goes back to zero and there’s no common prefix or suffix. At that point we can’t let j go back any further, so we need to control the boundary case, so we only go back if j is greater than 0. If you get to zero and still don’t find a common prefix or suffix, you can move I forward one bit.
Note: we initially assign 0 to all values in the next array, so we don’t need to assign 0 to next when I and j don’t match and j is already subscript 0.
In the theory part, we said that the index 0 of the Next array is null after moving, so we need to add a -1. To keep moving, we finally add the logic Next [0] = -1.
One more thing to note here is that our loop cutoff condition is pattern.length-1, not pattern.length. This is because we’ve moved the prefix array one bit further back. So if we use the pattern. Length condition, if we have 11 letters in total, we call next[11 + 1] = j when we loop to I = 11, which naturally creates an extra value. And that’s what we need. Therefore, we can change the cut-off condition to pattern. Length-1.
The dynamic effect of this logic is as follows:
function kmp(source, pattern) {
// Compute the Next array
let next = new Array(pattern.length).fill(0);
// Look for common prefixes in patterns
let i = 1,
j = 0;
while (i < pattern.length - 1) {
if (pattern[i] === pattern[j]) {
++j, ++i;
next[i] = j;
} else {
if (j > 0) {
j = next[j];
} else {
++i;
}
}
}
next[0] = -1;
console.log(next);
}
kmp(' '.'ababaaababaa');
Copy the codeLet’s call KMP to see if the final next array is correct.
Perfect, so we’re where we want our next array to be. The next step is to implement our matching logic.
matching
In fact, the matching logic is basically similar to the logic we used to calculate the Next array. The big difference is that instead of comparing the pattern string to its own character, it now compares the original character.
In this matching loop, we need to use I and j again, so we actually have conflicting scopes. So we’re using a little trick here, where we evaluate the Next array code with {} wrapped around it so that the I and j in it are limited to this part of the code. Then our matching code is the same, with {} wrapped around it.
The matching logic is that we both need to start at the index 0 for I and j.
And then our loop will keep going until I reaches the length of our original string.
The logic in the loop is as follows:
- First of all, we judge the success of the match,
Pattern stringIn thejThe character pointing to andThe original stringδΈiWith the same character,iεjSo you can move one to the right and continue to match. - According to the way we analyze KMP tracebacks, we need to move the common prefix of the preceding character to the common suffix, so we can use the calculated value
nextArray values:j = next[j]Move. - But there is another case where the current j is subscript 0, in which case there can be no common prefix or suffix at all. In this case we can just look for the next character in the string to match the character at subscript 0 of our pattern string, so here it is
++iCan. - So let’s determine whether the current position of j must reach the last bit of the pattern string. If so, it proves that we have matched successfully.
- If all the characters of the original string are used, the pattern string has not been matched, which proves that no substring in the original string is the same as our pattern string, and the match fails immediately.
Following the logic above, our code looks like this:
function kmp(source, pattern) {
// Compute the Next array
let next = new Array(pattern.length).fill(0);
{
// Look for common prefixes in patterns
let i = 1,
j = 0;
while (i < pattern.length - 1) {
if (pattern[i] === pattern[j]) {
++j, ++i;
next[i] = j;
} else {
if (j > 0) {
j = next[j];
} else {
++i;
}
}
}
next[0] = -1;
}
/ / match
{
let i = 0,
j = 0;
while (i < source.length) {
if (pattern[j] === source[i]) {
++j, ++i;
} else {
if (j > 0) {
j = next[j];
} else{ ++i; }}if (j === pattern.length) return true;
}
return false; }}console.log(kmp('ABABABAABABAAABABAA'.'ABABAAABABAA'));
console.log(kmp('helbbblo'.'ll'));
Copy the codeFinally we performed this different character matching example. If the code for our KMP algorithm is correct, the first character match should succeed and the second should fail. So let’s do it and see if it works.
This is obviously true. So we have completed the code implementation of the KMP algorithm.
Hopefully this article will give you a better understanding of the KMP algorithm, to be honest, because there are many tutorials, many articles on this algorithm. However, I have read a lot, and the basic concepts are different, such as prefix, PMT and next. After my research, in fact, the final implementation is actually the same, in fact, it is better to understand. For me, the concepts of prefix and next are best understood.
This article takes the longest time among all my articles, and I have rewritten it for three times in total. Because of the differences of different KMP articles, I made many mistakes in the beginning of sorting out, which made my knowledge of KMP more and more confused. Finally, I read a lot of videos and articles, and then STUDIED them one by one before I really understood them. If this article gives you a clearer understanding of KMP, please give me a thumbs up. Thanks
Bloggers are learning live at station B. Welcome to live Studio.
We are here to supervise each other, encourage each other, and strive to embark on the road of learning in life, so that learning changes our life!
It is boring and lonely on the way to study, but I hope it can bring us more company and more encouragement. Let’s refuel together! (ΰΉ β’ Μ γ Μ) organisation
I’m Three Diamonds from Tech Galaxy, a tech guy who is reinventing knowledge. See you next time.