Prefix function stores the information about how sought pattern matches itself after the shift. To use the information about previous matches, KMP algorithm uses a prefix function. Knuth-Morris-Pratt algorithm is one of the most popular effective string matching algorithms. Knuth-Morris-Pratt algorithm (KMP Algorithm) All of them perform some kind of pre-processing of the sought string before the search phase. There are several effective string matching algorithms that use the information about previous matches. For example, if we are searching for the substring M = “ aaab” and we have found a match at offset k = 0, there certainly cannot be any match at offsets 1, 2, 3 because S = ‘b’. The major problem with the described algorithm is that it discards the information that was acquired for previous values of k. The running time of simple string matching is O( len(M) * ( len(S) - len(M) - 1)). This algorithm is illustrated in the following picture. S with corresponding characters from the sought string ( M. The simplest string matching algorithm works as follows:įor each possible offset k within a string S ( k is a number in range from 0 to len(S) - len(M)) compare characters S.
Let’s assume, we have a string S and a sought string (or pattern) M. Choosing String Matching Algorithm Simple String Matchingįirst, let’s consider the simplest possible algorithm for string matching. The next section of this article is dedicated to choosing an appropriate algorithm for our library. There are several algorithms for string matching. Also, information about positions of found terms in input text may be useful.īefore evaluating search query, we must find all occurrences of search terms in input text. The purpose of our library is to determine if given text matches given search query. For example, this approach is used in the web search engines.
0 kommentar(er)
