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
| class Rabin_Karp {
constructor(str) {
this._origin = str.split("")
this._len = str.length
}
matchResult(str) {
let result = [],
hash = this._hash(str),
strLen = str.split("").length
console.log(strLen)
for (let i = 0, len = this._len - strLen + 1; i < len; i++) {
let tmp = this._origin.slice(i, i + strLen).join("")
if (hash === this._hash(tmp) && this._compare(str, tmp)) {
result.push(i)
}
}
return result
}
_hash(string) {
let hash = 5381
string
.toString()
.split("")
.map((i) => (hash = (hash << 5) + hash + i.charCodeAt(0)))
return hash
}
_compare(arr1, arr2) {
for (let i = 0, len = arr1.length; i < len; i++) {
if (arr1[i] != arr2[i]) return false
}
return true
}
}
let matching = new Rabin_Karp("tetesteestfdjklsajtest2tese3trtessstest")
console.log(matching.matchResult("test"))
|