Algorithms & Data Structures - Day 3April 05, 2020

Yesterday, I learned about

  • Big O of Objects and Arrays
  • Common algorithms & problem solving patterns
  • Searching algorithms

Today, I learned about Knuth–Morris–Pratt (KMP) search algorithm. It’s a more efficient way to search for a pattern of text given a larger group of strings. It took a little time to master the steps, but after then, I was more bothered with writing the algorithm in JavaScript. I learn so much by watching these videos on Youtube, you can check them out

I’m not going to write much about this algorithm at the moment, honestly because I don’t understand it well enough to explain 🙇‍♂️.

But Here’s The code

let = longestPrefixSuffix => {
  let table = new Array(pattern.length)
  let pointer = 0
  table[0] = 0

  for (let i = 1; i < pattern.length; i++) {
    while (pointer > 0 && pattern.charAt(i) !== pattern.charAt(pointer)) {
      pointer = table[pointer - 1]
    }

    if (pattern.charAt(i) === pattern.charAt(pointer)) {
      pointer++
    }
    table[i] = pointer
  }
  return table
}

let match = (text, pattern) => {
  let prefixes = longestPrefix2(pattern),
    matches = []

  let j = 0,
    i = 0

  while (i < text.length) {
    if (text.charAt(i) === pattern.charAt(j)) {
      i++
      j++
    }

    if (j === pattern.length) {
      matches.push(i - j)
      j = prefixes[j - 1]
    } else if (text.charAt(i) !== pattern.charAt(j)) {
      if (j !== 0) {
        j = prefixes[j - 1]
      } else {
        i++
      }
    }
  }

  return matches
}

I’ll put out comments to the code as soon as possible. You can also see a github gist here