Fully master the KMP algorithm ideology

People who have learned the data structure are quite impressed by the KMP algorithm. Especially new hands, it is difficult to understand its meaning and get a mist. Today we will face it, don't understand it completely, and swear.

Today, everyone is basically using Yan Weimin's book, then I will tell the KMP algorithm. (The younger brother is preparing for the postgraduate study, in order to save time, I have omitted it here, I will make it back.) Strict "Data Structure" 79 pages tell the basic matching method, this is the foundation. Let this understand this first. On the 80-page, the beginning of the KMP algorithm has given an example, let us have the original idea of ​​KMP. The purpose is to point out that "thereby, the I pointer is not backtick throughout the match,". We continue to see: The general situation is now discussed. Suppose the primary string: s: 's (1) s (2) s (3) ... s (n)'; mode string: p: 'p (1) p (2) p (3) ... ..p ( m) 'After reading this paragraph, continue

Now we assume that the primary string of the first character and the mode string of J (J <= m) characters 'mismatch', the primary string of the first character and the second character of the mode string continue to be compared

At this time, s (i) ≠ p (j),

Main string: s (1) ... S (i-j 1) ... S (i-1) s (i) ................ || (match) || (失 配) matching string: P (1) ... p (j-1) p (j)

Thus, we get the relationship 'p (1) p (2) p (3) ... ..p (j-1)' = 's (i-j 1) ... S (i-1)'

Since S (i) ≠ p (j), S (i) will continue to compare with P (k), then the substrings of the previous (k-1) character in the mode string must meet the following relationship, and not There may be k '> K to meet the following relations: (k

which is:

Main string: s (1) ... s (ik 1) s (IK 2) ... S (i-1) s (i) .............. || (match) || ||? Comparison) Matching string: p (1) p (2) ... p (k-1) p (k)

Now we integrate the relationship between the previous summary

Have:

S (1) ... s (ij 1) ... s (ik 1) s (ik 2) ... S (i-1) s (i) ... || (match) || || || (Display) P (1) ... p (j-k 1) p (j-k 2) .... p (j-1) p (j) || (match) || || ? (To be compared) P (1) p (2) .... p (k-1) p (k)

From the top, we get the relationship: 'p (1) p (2) p (3) ... ..p (k-1)' = 's (j-k 1) s (J-K 2) ...... S (J-1) 'Next, "reverse, if there is a paragraph that satisfies the formula (4-4) ..." in the pattern string. After reading this paragraph, if you don't understand below, you don't want to see it. Go directly to the source program of the next NEXT function. (Fake code)

K is related to next, but when you first see, you don't have to investigate how much K is, as for how the NEXT value is coming out, I teach you how to learn. Don't there be an example in the textbook 83? That is, Figure 4.6 You look at the source program, watching the example slowly launching it. See if you do is the same as the correct NEXT value on the class. Then look for a few exercises, practice, and be sure to do it. Now your mind has already initially thoughtful, then go back to see how it is pushing, if you don't understand, continue doing exercises, do it again. trust yourself! ! ! Attachment: KMP algorithm looks out the number of string S in string P count #include #include #include using namespace std;

Inline void next (const string & t, vector & next) {// Press mode string to generate vector, next (t.size ()) Next [0] = - 1; for (int i = 1; i = 0) j = next [j]; // recursive calculation IF (t [i] == t [j 1]) Next [i] = j 1; else next [i] = 0; //}} inline string :: size_type count_kmp (Const String & S, Const String & T ) {// Using the NEXT function of the mode String T, the number of counts of counts in the primary string S is KMP algorithm // where T is non-empty, Vector Next (T.Size ()); Next (t, Next ); String :: size_type index, count = 0; for (index = 0; index