String Pattern Matching Algorithm. Part-2
Knuth–Morris–Pratt(KMP) algorithm, Z-algorithm, Rabin–Karp algorithm, Tries.
In part-1 I try to explain KMP. So, now let’s talk about Z-algorithm. KMP and Z-algorithm are almost same. Z-algorithm try to find the maximum length of character start from i-th position which are same from 0-th position character. Here we try to explain the optimal way to implement the Z-algorithm.
let’s assume we get a range l and r for a index i for which we get maximum match. We have an array z-array. The value of each index represent the maximum match or maximum prefix which found from that index. Now let’s see different cases.
Case 1: if i>R. We set L,R = i and try to match the value from 0-th index. Incrementing R till we found the match. Finally update the value of Z-Array[i] = R-L+1.
Case 2: i can be within l to r.
What is it mean? We can reach some decision from here. As we iterate S7 value so we already have Z-array value of S0-S6 index. As the range is (L-R) S4 to S9. Total elements is R-L+1 = 9 - 4 + 1 = 6 element. So 6 element starting from 0 index are equal to them. S0 - S5 is equal to S4 - S9 . So when I am in i-th position, I already know i - L = 3 , first 3 element index (0–2)is equal to L-i except i. Index 3 is also equal to i-th index but we want to know the Z-Array value of index 3. That value, says us how many element he(index-3) find out match prefix from that position. If the value Z-Array[i-L] < R-i+1 it means the matching prefix from position i-L is not bigger than our known range(R-i+1) which is match and we can confirm it. So Z-Array[i] = Z-Array[i-L]. if it is bigger than it means the matching prefix from position i-L is bigger than our known range(R-i+1). But we can not so sure that it will match from position R too. It may match or may not be. So what we can do is to update the L position to i and try to find out maximum number of match from S[R-L] == S[R]. Keep increasing R till it match. When finish we get the maximum number of prefix which match for i-th position. So Z-Array[i] = R-L+1.
Final output of an example
Let’s see the code:
Time Complexity:
Here we traverse the string. We never decrement the value of R. It is always incrementing. So the time complexity of Z-algorithm will be O(n).
Thanks for reading. Let me know if you have any question or find out any mistake done by me. I will try to response and update soon. Rabin–Karp algorithm, Tries will discuss letter parts. Happy coding.
