KMP match string

One 、 Preface

This chapter records your own learning KMP A note of the algorithm . I think KMP Although there is no relevant algorithm used at present , But his thought is wonderful , Many people will not understand the origin of this algorithm at the beginning . And I also wrote several times to really say that I have mastered some KMP Algorithm . In fact, the main thing to remember is ,KMP Completed an idea of comparing the string with itself .

All string subscripts are from 1 Start

Two 、 The relevant operation

① Definition of related variables

To be honest, I think the definition of some related arrays is the core of the whole algorithm

The first is the two strings given by the topic , A longer one is called a pattern string , The other is called substring , The requirement of the topic is the position or number of occurrences of the substring in the pattern string

Let's look at the most difficult one ne Definition of array , The common prefix length of the longest substring

In fact, this place needs a definition , hypothesis ne[X], This actually represents , Substring from 1-X The length of the longest common prefix of the string of position . The point here is , What is a front and back affix

• Prefix : A continuous substring containing the first letter of a string
• suffix : A continuous substring containing the last letter of the string

Like strings ：abc

The prefix is : a ab

The suffix is : c bc

②ne Solving arrays

Find out the prefix and suffix , If we want to ask ne How to find an array ？

Suppose we have a string ：abcabf

a : 0

ab : 0

abc : 0

abca : a Is the public prefix 1

abcab: ab Is the public prefix 2

abcabf: 0

And finding such an array above is to compare p The string itself , The matching diagram is as follows ：

The code is as follows ：

for(int i = 2, j = 0; i <= n; i ++ ) {
        while(j != 0 && p[j + 1] != p[i]) j = ne[j];
        if(p[j + 1] == p[i]) j ++ ;
        ne[i] = j;
    }

③ string matching

Why find a ne Arrays can be used for matching ？

This is one of my most commonly used comprehension charts

We can see that there are two substrings

• q : abcabcabf
• p : abcabf

When p Match to f When I found that it was not equal , So substring p The location of the restart match is determined by ne Array to indicate ,f Position the previous position is b,b Of ne The value is 2, The length of the public pre suffix representing this position is 2, Then we need to go back to 2 The location of , That is to say p In a string b Location , Look again b hinder c Whether it is equal to the above string . After equality, continue to move forward to match p Pointer to the string of j, know j The value of the pointer is equal to p The length of , It indicates that the match has been successful .

The reason why the above can be carried out , In fact, it's because ,p utilize ne Pointer to indicate the prefix that has been matched , We will not re match , Instead, start again with the matching prefix , in other words ,abf and q List of abc The strings are not equal , however abc It's a perfect match ab suffix , What about mine p There is just one in the string ab Prefix , Let's go straight from ab The position of this prefix will continue to match later , This avoids the time complexity of repeated matching ！

3、 ... and 、 Related topics

complete AC Code

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100050, M = 10 * N;
char p[N], q[M];
int ne[N];

int main() {
    // Make relevant input 
    int n, m;
    cin >> n >> (p + 1) >> m >> (q + 1);
    
    // Progressiveness ne Solving arrays 
    for(int i = 2, j = 0; i <= n; i ++ ) {
        while(j != 0 && p[j + 1] != p[i]) j = ne[j];
        if(p[j + 1] == p[i]) j ++ ;
        ne[i] = j;
    }
    
    // Match strings 
    for(int i = 1, j = 0; i <= m; i ++ ) {
        while(j != 0 && p[j + 1] != q[i]) j = ne[j];
        if(p[j + 1] == q[i]) j ++ ;
        if(j == n) {
            cout << i - n << " ";
            j = ne[j];
        }
    }
    
    return 0;
}