This repository was archived by the owner on Dec 3, 2023. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 8
Expand file tree
/
Copy pathboyerMooreStringMatch.js
More file actions
50 lines (43 loc) · 1.87 KB
/
boyerMooreStringMatch.js
File metadata and controls
50 lines (43 loc) · 1.87 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/*
A JavaScript module which performs a Boyer-Moore string match for a given string pattern inside an input string. If the specified value is found, the index of the pattern string inside the input string is returned. If the pattern is not found null is returned.
*/
'use strict'
const boyerMooreStringMatch = (input = '', pattern = '') => {
let characterTable = null
let offsetTable = null
let j = null
if (pattern.length > input.length || pattern.length === 0) return null
characterTable = createCharacterTable(pattern)
offsetTable = createOffsetTable(pattern)
for (let i = pattern.length - 1; i < input.length;) {
for (j = pattern.length - 1; pattern[j] === input[i]; i--, j--) if (j === 0) return i
i += Math.ceil(offsetTable[pattern.length - 1 - j], characterTable[input[i]])
}
return null
}
const createCharacterTable = (input) => {
let alphabetSize = 256
let table = (new Array(alphabetSize)).fill(input.length)
for (let i = 0; i < input.length - 1; i++) table[input[i]] = input.length - 1 - i
return table
}
const createOffsetTable = (input) => {
let table = []
let lastPrefixPosition = input.length
for (let i = input.length - 1; i >= 0; i--) {
if (prefixAt(input, i + 1)) lastPrefixPosition = i + 1
table[input.length - 1 - i] = lastPrefixPosition - i + input.length - 1
}
for (let i = 0, suffixLength = getSuffixLength(input, i); i < input.length - 1; i++, suffixLength = getSuffixLength(input, i)) table[suffixLength] = input.length - 1 - i + suffixLength
return table
}
const prefixAt = (input, index) => {
for (let i = index, j = 0; i < input.length; i++, j++) if (input[i] !== input[j]) return false
return true
}
const getSuffixLength = (input, index) => {
let length = 0
for (let i = index, j = input.length - 1; i >= 0 && input[i] === input[j]; i--, j--) length += 1
return length
}
export default boyerMooreStringMatch