GeezerVison is showing github.com — JavaScript/String/BoyerMoore.js at master · QueenYu/JavaScript

Expand file tree

BoyerMoore.js

Copy path

More file actions

Latest commit

History

49 lines (48 loc) · 1.27 KB

BoyerMoore.js

Copy path

File metadata and controls

49 lines (48 loc) · 1.27 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

*Implementation of the Boyer-Moore String Search Algorithm.

*The Boyer–Moore string search algorithm allows linear time in

*search by skipping indices when searching inside a string for a pattern.

**/

const buildBadMatchTable = (str) => {

const tableObj = {}

const strLength = str.length

for (let i = 0; i < strLength - 1; i++) {

tableObj[str[i]] = strLength - 1 - i

}

if (tableObj[str[strLength - 1]] === undefined) {

tableObj[str[strLength - 1]] = strLength

}

return tableObj

}

const boyerMoore = (str, pattern) => {

const badMatchTable = buildBadMatchTable(pattern)

let offset = 0

const patternLastIndex = pattern.length - 1

const maxOffset = str.length - pattern.length

// if the offset is bigger than maxOffset, cannot be found

while (offset <= maxOffset) {

let scanIndex = 0

while (pattern[scanIndex] === str[scanIndex + offset]) {

if (scanIndex === patternLastIndex) {

// found at this index

return offset

}

scanIndex++

}

const badMatchString = str[offset + patternLastIndex]

if (badMatchTable[badMatchString]) {

// increase the offset if it exists

offset += badMatchTable[badMatchString]

} else {

offset++

}

return -1

}

export { boyerMoore }