Correct in an article on the part of the code matching table algorithm implementation @ sea_ljf timely correct) (thanks to a net friend, I’m sorry to give you an error message, want to be mislead students be able to see this article, epsilon = epsilon = epsilon = ┏ (゜ ロ ゜;) ┛.

One, foreword

Given a Haystack string and a Needle string, find the first position in the Haystack string where the Needle string appears (starting from 0). If none exists, -1 is returned.

This is the double pointer Easy [28. Implement strStr()], although it is an Easy label topic, but string matching as one of the most widely studied problems in computer science, the relevant algorithm is also very much.

This article mainly takes you to understand the implementation process and code implementation of KMP string matching algorithm.

2. Naive string matching algorithm

Before introducing the KMP string matching algorithm, let’s first understand the implementation of the naive string matching algorithm:

The idea of the above code is to match the needle string with the substring of the Haystack string in order, the time complexity is O(nm).

3. KMP string matching algorithm

1. KMP algorithm execution process

     
    
      
      haystack: aabaaabaaac
    
      
        needle: aabaaac
    
     
Copy the code

Taking the above-mentioned Haystack and Needle as examples, we will take you through the implementation process of KMP algorithm.

Before executing the KMP string matching algorithm, we need to preprocess the Needle and calculate the partial matching table of the Needle:

This table records the length of the longest common string with incomplete prefixes for all the prefixes in the Needle string (a mouthful,,ԾㅂԾ,,).

The needle string is prefixed with: A, AA, aab, aaba, aABAA, aABAAA, aabaaAC.

Take the prefix aabaa as an example:

  • Incomplete prefixes include a, AA, aab, aaba;

  • Incomplete suffixes include a, aa, baa, abaa;

So the longest common string for aABaa incomplete prefixes has a length of 2.

Once you understand the concept of partial matching tables, do the first round of matching:

As shown in the figure above, the Needle string cannot be matched at this point. The naive matching algorithm should move the start pointer in Haystack back one bit and compare the Haystack and Needle strings in turn.

Unlike the naive matching algorithm, the KMP algorithm will first get the longest common string length of the current position based on the partial matching table (the maximum length can be obtained from the above partial matching table is 2), and then align the needle string with the current haystack matching position of the subscript 2. And instead of starting from the beginning, match directly from the position backwards:

In this way, the KMP algorithm can determine the result of string matching in the second round.

Compared with the naive string matching algorithm, the KMP string matching algorithm reduces the time complexity to O(n+m).

2. Implementation of partial matching table algorithm

Partial matching table is the core of the whole KMP algorithm, and its implementation also adopts the two-pointer technique:

  • Create two before and after Pointers: start and end;

  • The start pointer is responsible for the position of the longest public string in the incomplete prefix.

  • The end pointer is mainly responsible for traversing the prefix in the needle;

3. Implementation of KMP string matching algorithm

KMP string matching algorithm also uses the double-pointer technique in the whole matching process:

  • A pointer iterates through the haystack string;

  • A pointer iterates through the Needle string;

If the characters in the haystack string are not equal to the characters in the needle string, then we need to query the partial matching table and move the needle string pointer to the appropriate position for the next round of matching:

At this point, we have implemented the KMP string matching algorithm. If you are still confused by the blogger’s rough explanation, you can search the following references:

  • Ruan Yifeng’s Network Log — KMP algorithm for String Matching

  • The Knuth-Morris-Pratt Algorithm in my own words

Write in the last

Algorithms as basic computer disciplines, using JavaScript brush, there is no loss of ε=ε=ε= old (゜ _ ゜ロ゜;) ┛.

This series of articles will provide summaries of each algorithm on three levels of difficulty (easy, medium, and hard). In the simple difficulty, we will introduce the basic knowledge and implementation of the algorithm, and in the other two difficulties, we will focus on the idea of solving the problem.

In each summary, some key topics will be selected and explained. For a complete list of problems, please refer to “LeetCode Journey of Front End Engineers”.

If this article has helped you, feel free to like it or follow it to encourage bloggers.

  • LeetCode Journey for front-end Engineers — Two-pointer Tips Easy

  • Front-end engineers LeetCode trip [https://github.com/15751165579/LeetCode]

Focus on not getting lost.

Quality content we all “watch”