# Algorithms & Data Structures - Day 3April 05, 2020

• 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

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