KMP string matching algorithm

KMP 算法本质

This is a very good KMP algorithm article if you can read Chinese: KMP algorithm.  But it still doesn't clear state what known information is used to reduce comparison. I figured this out by myself.  The "known information" is the longest unique substring.



Last Step










The naive  solution what it fails to match ' ' with 'D', it will reset j = 0, and i = 5 to re-match the whole string from beginning. Therefore the "known information" S[5] == P[1] == B, S[6] == P[2] == C,
S[7] == P[3] == D, and S[8] == P[4] == A is discarded.  The KMP algorithm is utilizing this info to reduce comparison. Since we know P[0] != P[1] != P[2] != P[3] and P[0] == P[4] == A,  there is no necessary to compare P[0] with S[5], S[6], S[7], S[8]. Why? Because we know S[5] == P[1] == B, and P[0] != P[1], therefore, P[0] != S[5], similarly, P[0] cannot be S[6], S[7] either. Since P[0] == P[4] == A, we cannot skip S[8], that's why we start with S[8] as the next comparison point. The next array used to calculate the S[8] position.














Comments

Post a Comment

Popular posts from this blog

zhitongguigu

Lecture 1: To do: (117? 199) Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree . In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree. numerical_limits<int>::min()   <==> INT_MIN
Read more

Array Part2

Two pointers 977 Squares of a Sorted Array      We can use two pointers to read the positive and negative parts of the array - one pointer  j  in the positive direction, and another  i  in the negative direction. Now that we are reading two increasing arrays (the squares of the elements), we can merge these arrays together using a two-pointer technique. 11 Container With Most Water      O(N) time and O(1) space, since better candidadates must use the taller line of l and r therefore we can use two pointer keep moving towards each other until they meet. Always abandon the shorter line while moving. 80 Remove Duplicates from Sorted Array II      tail = 0; for (int i = 0;  i < nums.size(); i++)           if (i < 2 || nums[i] > nums[tail - 2]) // not included twice yet                 nums[tail++] = nums...
Read more

Two pointers (Part 1)

344 Reverse String      Use two pointers i, j. keep switching elements at position i, j while i < j.     string reverseString(string s) {        for (int i = 0, j = s.size() - 1; i < j; i++, j--)            swap(s[i], s[j]);                  return s;     } 345 Reverse Vowels of a String      Similar with 344  Reverse String ,  except we need to guard the swap operation conditionally based on whether the current two chars are vowels or not. 283 Move Zeroes      Use two pointers, the front iterates the elements in the array. while the tail one keeps the current store position. If front is not zero, store it to the tail position and increase tail pointer. After the loop, set all the remaining with zero. 349 Intersection of Two Arrays      ...
Read more