GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — Added Rabin-Karp Algorithm · tttamaki/AlgorithmVisualizer@018c47b

File tree

Expand file treeCollapse file tree
Open diff view settings
Filter options
  • algorithm
    • category.json
    • string/rabin_karp_algorithm
      • basic
        • code.js
        • data.js
      • desc.json
Expand file treeCollapse file tree
Open diff view settings
Collapse file

‎algorithm/category.json‎

Copy file name to clipboardExpand all lines: algorithm/category.json
+2-1Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -50,7 +50,8 @@
5050
"name": "String",
5151
"list": {
5252
"edit_distance": "Edit Distance",
53-
"knuth_morris_pratt": "KMP Substring Search"
53+
"knuth_morris_pratt": "KMP Substring Search",
54+
"rabin_karp_algorithm": "Rabin-Karp Algorithm"
5455
}
5556
},
5657
"dp": {
Collapse file

‎algorithm/string/rabin_karp_algorithm/basic/code.js‎

Copy file name to clipboard
+57Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
var N = text.length;
2+
var M = pattern.length;
3+
4+
var hashText = 0; //hash value for text
5+
var hashPattern = 0; //hash value for pattern
6+
var h = 1;
7+
8+
for ( var i = 0; i < (M - 1); i++ ) {
9+
h = ( h * D ) % Q;
10+
}
11+
12+
for ( var i = 0; i < M; i++ ) {
13+
hashPattern = ( D * hashPattern + pattern[i].charCodeAt(0)) % Q;
14+
hashText = ( D * hashText + text[i].charCodeAt(0)) % Q;
15+
}
16+
17+
for ( var i = 0 ; i <= N-M; i++ ) {
18+
19+
/*
20+
Check if hash values of current window of text matches
21+
with hash values of pattern. If match is found then
22+
check for characters one by one
23+
*/
24+
if ( hashPattern === hashText ) {
25+
var f = 0;
26+
tracer1._select( i, i + M )._wait();
27+
tracer2._select( 0, M - 1 )._wait();
28+
for( var j = 0; j < M; j++ ) {
29+
30+
tracer1._notify( i + j )._wait();
31+
tracer2._notify( j )._wait();
32+
if ( text[i + j] != pattern[j] ) {
33+
f++;
34+
}
35+
tracer1._denotify( i + j );
36+
tracer2._denotify( j );
37+
}
38+
39+
if( f === 0 ) {
40+
logger._print( ' Pattern found at index ' + i );
41+
}
42+
tracer1._deselect( i, i + M );
43+
tracer2._deselect( 0, M - 1 );
44+
}
45+
46+
/*
47+
Calculate hash value for next window of text :
48+
*/
49+
if ( i < N-M ) {
50+
hashText = ( D * ( hashText - text[i].charCodeAt(0)*h ) + text[ i + M ].charCodeAt(0) ) % Q;
51+
52+
// Convert negative value of hashText (if found) to positive
53+
if ( hashText < 0 ) {
54+
hashText = hashText + Q;
55+
}
56+
}
57+
}
Collapse file

‎algorithm/string/rabin_karp_algorithm/basic/data.js‎

Copy file name to clipboard
+9Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
var text = ['h','e','l','l','o',' ','s','i','r',' ','h','e','l','l','o'];
2+
var pattern = ['h','e','l','l','o'];
3+
4+
var Q = 101; // A prime number
5+
var D = 256; // number of characters in the input alphabet
6+
7+
var logger = new LogTracer();
8+
var tracer1 = new Array1DTracer('Text')._setData(text);
9+
var tracer2 = new Array1DTracer('Pattern')._setData(pattern);
Collapse file

‎algorithm/string/rabin_karp_algorithm/desc.json‎

Copy file name to clipboard
+16Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
{
2+
"Rabin–Karp Algorithm": "Rabin–Karp algorithm or Karp–Rabin algorithm is a string searching algorithm created by Richard M. Karp and Michael O. Rabin (1987) that uses hashing to find any one of a set of pattern strings in a text.",
3+
"Applications": [
4+
"Substring Search"
5+
],
6+
"Complexity": {
7+
"time": " O(N) : If a sufficiently large prime number is used for the hash function. O(MN) : Worst Case ",
8+
"space": "O( 1 )"
9+
},
10+
"References": [
11+
"<a href='https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm'>Wikipedia</a>"
12+
],
13+
"files": {
14+
"basic": "Rabin-Karp Algorithm"
15+
}
16+
}

0 commit comments

Comments
0 (0)
You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.