FilesExpand file tree

 main

/

KMPPatternSearching.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

55 lines (48 loc) · 1.42 KB

 main

/

KMPPatternSearching.js

Copy path

Top

File metadata and controls

• Code
• Blame

55 lines (48 loc) · 1.42 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

50

51

52

53

54

55

// Implementing KMP Search Algorithm to search all the instances of pattern in

// given text

// Reference Book: Introduction to Algorithms, CLRS

// Explanation: https://www.topcoder.com/community/competitive-programming/tutorials/introduction-to-string-searching-algorithms/

const computeLPS = (pattern) => {

const lps = Array(pattern.length)

lps[0] = 0

for (let i = 1; i < pattern.length; i++) {

let matched = lps[i - 1]

while (matched > 0 && pattern[i] !== pattern[matched]) {

matched = lps[matched - 1]

}

if (pattern[i] === pattern[matched]) {

matched++

}

lps[i] = matched

}

return lps

}

/**

* Returns all indices where pattern starts in text

* @param {*} text a big text in which pattern string is to find

* @param {*} pattern the string to find

*/

const KMPSearch = (text, pattern) => {

if (!pattern || !text) {

return [] // no results

}

// lps[i] = length of proper prefix of pattern[0]...pattern[i-1]

// which is also proper suffix of it

const lps = computeLPS(pattern)

const result = []

let matched = 0

for (let i = 0; i < text.length; i++) {

while (matched > 0 && text[i] !== pattern[matched]) {

matched = lps[matched - 1]

}

if (text[i] === pattern[matched]) {

matched++

}

if (matched === pattern.length) {

result.push(i - pattern.length + 1)

matched = lps[matched - 1]

}

}

return result

}

export { KMPSearch }