KMP is an algorithm to find the occurrence of string 'W' in another string 'S'.
1. Creates a partial match table T. T[i] stores the length of the longest proper suffix of W[0..(i-1)] which is a proper prefix of W.
How T is used in the main KMP algorithm:
At any given time, the algorithm is in a state determined by two integers,
T indicates where we need to look for the start of a new match in the event that the current one ends in a mismatch. The entries of
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm#Efficiency_of_the_KMP_algorithm
1. Creates a partial match table T. T[i] stores the length of the longest proper suffix of W[0..(i-1)] which is a proper prefix of W.
How T is used in the main KMP algorithm:
At any given time, the algorithm is in a state determined by two integers,
m and i, which denote respectively the position within S which is the beginning of a prospective match for W, and the index in W denoting the character currently under consideration.
T indicates where we need to look for the start of a new match in the event that the current one ends in a mismatch. The entries of
T are constructed so that if we have a match starting at S[m] that fails when comparing S[m + i] to W[i], then the next possible match will start at index m + i - T[i] in S (that is, T[i] is the amount of "backtracking" we need to do after a mismatch).
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm#Efficiency_of_the_KMP_algorithm
No comments:
Post a Comment