javascript-algorithms/src/algorithms/string/rabin-karp/rabinKarp.js at master · JavaScriptExpert/javascript-algorithms · GitHub

Repository navigation

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

import PolynomialHash from '../../cryptography/polynomial-hash/PolynomialHash';

/**

* @param {string} text - Text that may contain the searchable word.

* @param {string} word - Word that is being searched in text.

* @return {number} - Position of the word in text.

*/

export default function rabinKarp(text, word) {

const hasher = new PolynomialHash();

// Calculate word hash that we will use for comparison with other substring hashes.

const wordHash = hasher.hash(word);

let prevFrame = null;

let currentFrameHash = null;

// Go through all substring of the text that may match.

for (let charIndex = 0; charIndex <= (text.length - word.length); charIndex += 1) {

const currentFrame = text.substring(charIndex, charIndex + word.length);

// Calculate the hash of current substring.

if (currentFrameHash === null) {

currentFrameHash = hasher.hash(currentFrame);

} else {

currentFrameHash = hasher.roll(currentFrameHash, prevFrame, currentFrame);

}

prevFrame = currentFrame;

// Compare the hash of current substring and seeking string.

// In case if hashes match let's make sure that substrings are equal.

// In case of hash collision the strings may not be equal.

if (

wordHash === currentFrameHash

&& text.substr(charIndex, word.length) === word

) {

return charIndex;

}

}

return -1;

}