Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitd74f242

Browse files
aladin002dzappgurueugithub-actions
authored
Rabin Karp Search Algorithm (TheAlgorithms#1545)
* Search: Rabin-Karp algorithm* Prettier Style* Search: Rabin-Karp adding reference* Search: Rabin-Karp styling and remove unecessary logging* Search: Rabin-Karp review notes* Simplify return* Updated Documentation in README.md---------Co-authored-by: Lars Müller <34514239+appgurueu@users.noreply.github.com>Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com>
1 parent889d9c3 commitd74f242

File tree

3 files changed

+95
-0
lines changed

3 files changed

+95
-0
lines changed

‎DIRECTORY.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -311,6 +311,7 @@
311311
*[LinearSearch](Search/LinearSearch.js)
312312
*[Minesweeper](Search/Minesweeper.js)
313313
*[QuickSelectSearch](Search/QuickSelectSearch.js)
314+
*[RabinKarp](Search/RabinKarp.js)
314315
*[SlidingWindow](Search/SlidingWindow.js)
315316
*[StringSearch](Search/StringSearch.js)
316317
*[TernarySearch](Search/TernarySearch.js)

‎Search/RabinKarp.js

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
/*
2+
* Implements the Rabin-Karp algorithm for pattern searching.
3+
*
4+
* The Rabin-Karp algorithm is a string searching algorithm that uses hashing to find patterns in strings.
5+
* It is faster than naive string matching algorithms because it avoids comparing every character in the text.
6+
*
7+
* This implementation uses a rolling hash function to efficiently compute the hash values of substrings.
8+
* It also uses a modulo operator to reduce the size of the hash values, which helps to prevent hash collisions.
9+
*
10+
* The algorithm returns an array of indices where the pattern is found in the text. If the pattern is not
11+
* found, the algorithm returns an empty array.
12+
*
13+
* [Reference](https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm)
14+
*/
15+
16+
constBASE=256// The number of characters in the alphabet
17+
constMOD=997// A prime number used for the hash function
18+
19+
functionrabinKarpSearch(text,pattern){
20+
constpatternLength=pattern.length
21+
consttextLength=text.length
22+
consthashPattern=hash(pattern,patternLength)
23+
consthashText=[]
24+
constindices=[]
25+
26+
// Calculate the hash of the first substring in the text
27+
hashText[0]=hash(text,patternLength)
28+
29+
// Precompute BASE^(patternLength-1) % MOD
30+
constbasePow=Math.pow(BASE,patternLength-1)%MOD
31+
32+
for(leti=1;i<=textLength-patternLength+1;i++){
33+
// Update the rolling hash by removing the first character
34+
// and adding the next character in the text
35+
hashText[i]=
36+
(BASE*(hashText[i-1]-text.charCodeAt(i-1)*basePow)+
37+
text.charCodeAt(i+patternLength-1))%
38+
MOD
39+
40+
// In case of hash collision, check character by character
41+
if(hashText[i]<0){
42+
hashText[i]+=MOD
43+
}
44+
45+
// Check if the hashes match and perform a character-wise comparison
46+
if(hashText[i]===hashPattern){
47+
if(text.substring(i,i+patternLength)===pattern){
48+
indices.push(i)// Store the index where the pattern is found
49+
}
50+
}
51+
}
52+
53+
returnindices
54+
}
55+
56+
functionhash(str,length){
57+
lethashValue=0
58+
for(leti=0;i<length;i++){
59+
hashValue=(hashValue*BASE+str.charCodeAt(i))%MOD
60+
}
61+
returnhashValue
62+
}
63+
64+
export{rabinKarpSearch}

‎Search/test/RabinKarp.test.js

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
import{rabinKarpSearch}from'../RabinKarp'
2+
3+
describe('Rabin-Karp Search',function(){
4+
it('should find the pattern in the text',function(){
5+
consttext='ABABDABACDABABCABAB'
6+
constpattern='DAB'
7+
constexpected=[4,9]
8+
9+
constresult=rabinKarpSearch(text,pattern)
10+
expect(result).to.deep.equal(expected)
11+
})
12+
13+
it('should handle multiple occurrences of the pattern',function(){
14+
consttext='ABABABABABAB'
15+
constpattern='ABAB'
16+
constexpected=[2,4,6,8]
17+
18+
constresult=rabinKarpSearch(text,pattern)
19+
expect(result).to.deep.equal(expected)
20+
})
21+
22+
it('should handle pattern not found',function(){
23+
consttext='ABCD'
24+
constpattern='XYZ'
25+
constexpected=[]
26+
27+
constresult=rabinKarpSearch(text,pattern)
28+
expect(result).to.deep.equal(expected)
29+
})
30+
})

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp