KMP string – explain the next array in simple terms

In fact, the ~ part we need to solve in the above figure, that is, s[0…j] is not only the prefix of s[0…2] = “aba”, but also s[0…2] = "aba", and want its length as long as possible, then s[0…j] is the best for s[0…2] The length is equal to the prefix and suffix. That is to say, you only need to make j = next[2], and then judge whether s[5] == s[j + 1] is true: if it is true, it means s[0…j + 1] is the longest equal prefix and suffix of s[0…5], let next[5] = j + 1; if not true , keep j = next[j] until j returns to -1, or on the way s[5] = = s[j + 1] established.

As shown in the figure above, j rolls back from 2 to next[2] = 0, and finds that s[5] == s[j + 1] is not true, so continue to let j roll back from 0 to next[0] = -1; Since j has rolled back to -1, it will not continue to roll back. At this time, it is found that s[i] == s[j + 1] is established, indicating that s[0...j + 1] is the longest equal prefix and suffix of s[0...5], so let next[5] = j + 1 = -1 + 1 = 0, and let j point to next[5].

The following summarizes the solution process of the next array and gives the code:

Initialize the next array, let j = next[0] = -1.
Let i traverse in the range of 1 ~ len - 1, for each i, execute 3, 4 to solve next[i].
Until j rolls back to -1, or s[i] == s[j + 1] is established, otherwise keep j = next[j].
If s[i] == s[j + 1], then next[i] = j + 1; otherwise next[i] = j.

next[0] = -1;
for (int i = 1, j = -1; i < len; i ++ )
{<!-- -->
    while (j != -1 & amp; & amp; s[i] != s[j + 1]) // prefix and suffix matching failed
    {<!-- -->
        // Repeatedly roll j back to -1, or s[i] == s[j + 1]
        j = next[j];
    }
    if (s[i] == s[j + 1]) // match succeeds
    {<!-- -->
        j + + ; // the longest equal suffix becomes longer
    }
    next[i] = j; // let next[i] = j
}

Please also be clear: we just did next array processing on a string! ! !

hello, kmp!

On this basis, we enter kmp. With the basis of finding the next array above, the kmp algorithm is following the gourd. Given a text string text and a pattern string pattern, and then judges whether the pattern string pattern is a substring of the text string string.
Take text = "abababaabc", pattern = "ababaab" as an example. Let i point to the current bit to be compared in text, and let j point to the last bit that has been matched in pattern, so that as long as text[i] == pattern[j + 1] is established, it means that pattern[j + 1] is also successful Match, at this time, add 1 to i and j to continue the comparison until j reaches m - 1 (m is the length of pattern), indicating that pattern is a substring of text. In this example, i points to text[4] and j points to pattern[3], indicating that pattern[0...3] has all been matched successfully. At this time, it is found that text[i] == pattern[j + 1] is established, which is It means that pattern[4] matches successfully, so add 1 to i and j.

Then continue to match. At this time, i points to text[5] and j points to pattern[4], indicating that pattern[0...4] has all been matched successfully. So try to judge whether text[i] == pattern[j + 1] is true: if it is true, then pattern[0...5] is successfully matched, and i and j can be added by 1 to continue to match the next bit. But here text[5] != pattern[4 + 1], the match fails. So what do we do here? Abandon the previous successful matching results of pattern[0…4], let j go back to -1 and start matching again? That's a brute force solution, let's take a look at how kmp handles it.

In order not to allow j to fall back directly to -1, it is necessary to seek to fall back to a j' closest to the current j (j is 4 at this time), so that text[i] == pattern[j' + 1] can be established, And pattern[0…j'] still matches the corresponding position of text, that is, pattern[0…j'] is the suffix of pattern[0…j]. This is easy to think of similar problems encountered in the previous nnext array. The answer is that pattern[0…j’] is the longest equal prefix and suffix of pattern[0…j]. In other words, you only need to keep j = next[j] until j falls back to -1 or text[i] == pattern[j + 1] is established, and then continue to match. The meaning of the next array is the position j should fall back to when j + 1 bit mismatch. For the example just now, when text[5] does not match pattern[4 + 1], let j = next[4] = 2, and then we will find that text[i] == pattern[j + 1] can be established, So let it continue matching until j == 6 also matches, which means pattern is a substring of text.

The general idea of the kmp algorithm is as follows:

1. Initialize j = -1, indicating the last bit of the pattern that is currently matched.
2. Let i traverse the text string text, and for each i, execute 3 and 4 to try to match text[i] and pattern[j + 1].
3. Until j rolls back to -1 or text[i] == pattern[j + 1], otherwise keep j = next[j].
4. If text[i] == pattern[j + 1], then let j ++. If j reaches pattern_len - 1, pattern is a substring of text.

// Omit the step of finding the next array
int j = -1; // means that no one has been matched yet
for (int i = 0; i < text_len; i ++ )
{<!-- -->
    while (j != -1 & amp; & amp; text[i] != pattern[j + 1])
    {<!-- -->
        j = next[j];
    }
    // text[i] matches pattern[j + 1] successfully, let j + 1
    if (text[i] == pattern[j + 1])
    {<!-- -->
        j + + ;
    }
    if (j == pattern_len - 1) // It is a substring, processed according to the requirements of the topic
}

If we observe the above analysis, can we find that:The process of solving the next array is actually the process of self-matching of the pattern string pattern.

Consider how to count the starting subscripts of pattern in text:
When j = m - 1, it means that the pattern matches completely, and at this time, i - j can be output (the end position of the text minus the length of the pattern is the subscript of the pattern in the text). But the question is: Where should the next match start in the pattern after ? Since multiple occurrences of pattern in text may overlap, it is not possible to add 1 to i to continue the comparison without doing anything, but to let j go back a certain distance first. At this time, next[j] represents the longest equal prefix and suffix of the entire pattern. From this position, let j be the largest, that is, make the matched part the longest, so as to ensure that there is no missing solution, and save a lot for the next match pointless comparison.

whyO(n + m)

We see that each i in the for loop has a while loop, so the number of j rollbacks may be unpredictable. Why is the time complexity of KMP O(n + m)?
First of all, i is continuously incremented by 1 in the whole for loop of kmp, so the number of changes of i in the whole process is O(m) level. Next, considering the change of j, we notice that j will only increase in one row, and Only add 1 each time, so that j can be increased by at most m times in the whole process; in other cases, j is constantly decreasing, since the minimum value of j will not be less than -1, so in the whole process, j can only be decreased by at most m times . That is to say, the while loop will only be executed at most m times for the whole process, so the number of j changes in the whole process is O(m) level. Since the number of times i and j change throughout the process is O(m), the overall complexity of the for loop part is O(m). Considering that calculating the next array requires a time complexity of O(n) (the analysis method is the same as above), the kmp algorithm requires a total time complexity of O(n + m).

Code (c++)

include <iostream>

using namespace std;

const int N = 1000010;
char p[N], s[N]; // use p to match s
// "next" array, if bit i stores value k
// Indicates that the last subscript of the prefix with the longest equal prefix and suffix in p[0...i] is k
// i.e. p[0...k] == p[i-k...i]
int ne[N];
int n, m; // n is the template string length m is the pattern string length

int main()
{<!-- -->
    cin >> n >> p >> m >> s;

    // There must be no equal prefixes and suffixes in the interval of p[0...0]
    ne[0] = -1;

    // Construct the next array of template strings
    for (int i = 1, j = -1; i < n; i ++ )
    {<!-- -->
        while (j != -1 & amp; & amp; p[i] != p[j + 1])
        {<!-- -->
            // If the prefix and suffix match is unsuccessful
            // Repeatedly make j go back until it reaches -1 or s[i] == s[j + 1]
            j = ne[j];
        }
        if (p[i] == p[j + 1])
        {<!-- -->
            j + + ; // When the match is successful, the longest equal suffix becomes longer, and the last digit of the longest equal suffix becomes larger
        }
        ne[i] = j; // Let ne[i] = j for easy calculation next[i + 1]
    }

    // kmp start !
    for (int i = 0, j = -1; i < m; i ++ )
    {<!-- -->
       while (j != -1 & amp; & amp; s[i] != p[j + 1])
       {<!-- -->
           j = ne[j];
       }
       if (s[i] == p[j + 1])
       {<!-- -->
           j ++ ; // When the match is successful, the template string points to the next bit
       }
       if (j == n - 1) // template string matching is complete, the subscript of the first matched character is 0, so n - 1
       {<!-- -->
           // When the match is successful, the end position of the text string minus the length of the pattern string is the start position
           cout << i - j << ' ';

           // The positions of the template strings in the pattern string may overlap
           // It is necessary to return j to a certain position, and then add 1 to i to continue the comparison
           // Falling back to ne[j] can ensure that j is the largest, that is, the part that has been successfully matched is the longest
           j = ne[j];
       }
    }

   return 0;
}

KMP string - explain the next array in simple terms