Description: The problem: string pattern matching algorithm--- KMP method: to find the position of the pattern string T from the main string S. Basic idea: from a character from the main string S and the first character of the mode string T if equal, continue to compare apples to apples Subsequent characters Otherwise, the next character from the main string and re-mode character comparisons and so on, until all of the characters of the pattern string T found in the main string S match, whereupon the matching is successful, otherwise the match is unsuccessful KMP algorithm can be completed in the level of O (n+m) the amount of time the pattern of the string matching operation. The improvement comprising: varying character comparisons, do not need to backtrack to the i pointer has been " partial match" results, derived from the use of sliding mode right as far a distance as possible whenever the trip matching process, continue comparison.
To Search:
File list (Check if you may need any files):
kmp.pdf
Download