FilesExpand file tree

 master

/

BoyerMoore.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

49 lines (48 loc) · 1.27 KB

 master

/

BoyerMoore.js

Top

File metadata and controls

• Code
• Blame

49 lines (48 loc) · 1.27 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/*

*

*

*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 }