This article is front-end internal sharing, refer to the article

1) What is KMP

An improved string matching algorithm

2. Violence matching

Contrast the target string (above) with the pattern string (below) one by one

      i
A B C A B D A B C E A B D
A B C E
      j               
Copy the code

When the difference is first detected

  i
A B C A B D A B C E A B D
  A B C E
  j               
Copy the code

3. What would a person do if they had to deal with it?

      i
A B C A B D A B C E A B D
      A B C E
      j               
Copy the code

Case 2

          i
A B C A B C D H I J K
A B C A B B
          j
Copy the code

mobile

          i
A B C A B C D H I J K
      A B C A B B
          k
Copy the code

Features:

  • I doesn’t backtrack, I just reposition j

Formula: P[0~k-1] == P[J-K ~ J-1]

The first k of the pattern string is equal to the first K of the position where j is located

The core of the KMP algorithm finds the left and right k (the next position of the J jump)

4. Get the code for the next jump location

Ideas:

  • Set a double pointer, the J pointer points to each element in turn, using the K pointer to calculate where J can jump
  • When the k pointer is equal to the J pointer, the two Pointers are added simultaneously. Otherwise move the k pointer to where it can be moved
  • Every comparison is to determine where j + 1 should jump
// Get the next location to jump to
function getNext (ps) {
  var next = []
  next[0] = -1 // initialize to -1
  let j = 0
  let k = -1
  while (j < ps.length - 1) {
    if (k == -1 || ps[j] == ps[k]) {
      next[j + 1] = k + 1 // if ps[j]==ps[k], then j+1 is k+1
      j++
      k++
    } else {
      // if ps[j] = next[k] and ps[k] = next[k]
      // Ps [j] == ps[k] next[j] == ps[k] next[j
      // If the first element is not equal, then k = next[k] will be equal to -1
      k = next[k]
    }
  }
  return next
}
Copy the code

For example,

              j
a b c d a b c a b
      k

// [ -1, 0, 0, 0, 0, 1, 2, 3, 1]
Copy the code

5. KMP algorithm

// ts main string; Ps substring
function KMP (ts, ps) {
  let i = 0 // The main string position
  let j = 0 // The position of the pattern string
  let next = getNext(ps) // Next is only about ps
  while (i < ts.length && j < ps.length) {
    if (j == -1 || ts[i] == ps[j]) {
      // When j is -1, we move I, and of course j returns to 0
      i++
      j++
    } else {
      j = next[j] Ps [0] = ts[j] = ts[j]}}if (j == ps.length) {
    return i - j // return the position of the first character of ps, I is the position of the last character of ps
  } else {
    return -1}}Copy the code

For example,

// The first one is different, I ++ I a b c d a b c a b b c d j // ts[I] and ps[j] the same I a b c d a b a b b c d j I a b c d a b a b b c d jCopy the code

6. Why not backtrack

  1. If you can’t guarantee that all of the previous elements match, it doesn’t make sense;
  2. If you go back and everything matches, you can definitely do that by moving j;

7. To summarize

KMS algorithm is to first find the pattern string when each character does not match the position that can jump to next, and then when comparing with the target string, if it is not the same, the pointer of the pattern string will point to the corresponding position of next, and then continue comparing.