KMP-Algorithm in C#
So my classmate and I attended a bad lecture about the Knuth-Morris-Pratt (KMP) Algorithm which left us totally confused.
We were given the following code for modelling the KMP https://dotnetfiddle.net/4Eta2t
We were to find a complete match for the pattern
ABCAAB in the text ABCABABABCAABAB
We also got a following table that simulates the change of the next array values over the iteration of KMP - this table threw us under the bus (see the attachment).
Could anyone help us to understand what is going on this table, basically?
So in the 1st iteration the char A is a match between the pattern and the text, the j is set to -1 because of this code line int i = 0, j = -1;
The index i is incremented in the cell B3. I got this. We shift the pattern 1 char to right.
In the 2nd iteration the index i is set to 1 and the index j is set to 0. We take two chars in the pattern and the text : pattern[i] = B and pattern[j] = A. Why were we comparing the these two chars in the same pattern??
The professor said, " look at this line else if (i < n && pattern[j] != text[i])this is why the next[j] is set to -1 " . we did not get this at all
From this point on we kept felling puzzled at this lecture.
Back to the 2nd iteration, the index i is set to 2 in the cell B6. Ok. incremented again.
In the 3rd iteration, we check two chars C at pattern[i] and A at pattern[j] = not a match either. At this point the index i is 2 and the index j 0. The next[j] stays -1 (why??)
We simply increment the index i once again to 3 in the cell B9.
In the 4th iteration, We compare two chars A at pattern[i] and A at pattern[j].
It is a match.
We increment the index i to 4, but from here I got confused. In the excel table the j is suddenly incremented to 1 (in the cell C11) and the next[i] is also incremented to 1 (in the cell D11). I don't get this sudden incrementation of the next and the index j.
so you saw our confusion. please help us comprehend this ultra conceptual lecture.KMP_Csharp | C# Online Compiler | .NET Fiddle
KMP_Csharp | Test your C# code online with .NET Fiddle code editor.
4 Replies
I followed this example to figure out the pattern table: https://youtu.be/V5-7GzOfADQ?t=725
And somewhat based off of: http://www-igm.univ-mlv.fr/~lecroq/string/node8.html#SECTION0080
Abdul Bari
YouTube
9.1 Knuth-Morris-Pratt KMP String Matching Algorithm
In P3, b is also matching , lps should be 0 1 0 0 1 0 1 2 3 0
Naive Algorithm
Drawbacks of Naive Algorithm
Prefix and Suffix of Pattern
KMP Algorithm
PATREON : https://www.patreon.com/bePatron?u=20475192
Courses on Udemy
================
Java Programming
https://www.udemy.com/course/java-se-programming/?referralCode=C71BADEAA4E7332D62B6
Da...
Knuth-Morris-Pratt algorithm
EXACT STRING MATCHING ALGORITHMS Animation in Java, Knuth-Morris-Pratt algorithm
The pattern table basically contains indexes in the pattern to fall back to when there's not a match.
I haven't touched the algorithm for like 5 years, so I can't really answer questions.
I still appreciate you for clarifying what the pattern table is about basically ✨
If you don't mind me asking again - I still have a trouble understanding why the KMP algorithm needs to fall back to when there's not a match. Is it actually what this algorithm should do or is it a function to prevent exceptions/overflow like out-of-range exception?
It's what the algorithm should do. You're precomputing work so that you don't need to fallback in the searched text itself.
You can imagine something like searching DNA sequences which only has "ATGC". You can often search for tens or 100+ bases for a gene across several million bases.
Such patterns have lots of repeats in them, so you can fallback to previous parts of the pattern more intelligently...which causes less work to be done while searching. Instead of merely advancing the searched string position by 1 (from the initial search location).
"Longest Proper Prefix which is Suffix (LPS)" is the algorithm to precompute the pattern table, apparently.