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
We also got a following table that simulates the change of the
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
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
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.
We were given the following code for modelling the KMP https://dotnetfiddle.net/4Eta2t
We were to find a complete match for the pattern
ABCAABABCABABABCAABABWe also got a following table that simulates the change of the
next 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])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 | Test your C# code online with .NET Fiddle code editor.
