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 — add rabin-karp algorithm · arshcoder13/Java@da44e42

File tree

Expand file treeCollapse file tree
Open diff view settings
Filter options
  • Programs
    • RabinKarp.java
Expand file treeCollapse file tree
Open diff view settings
Collapse file

‎Programs/RabinKarp.java‎

Copy file name to clipboard
+49Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
// Rabin-Karp algorithm in Java
2+
3+
public class RabinKarp {
4+
public final static int d = 10;
5+
6+
static void search(String pattern, String txt, int q) {
7+
int m = pattern.length();
8+
int n = txt.length();
9+
int i, j;
10+
int p = 0;
11+
int t = 0;
12+
int h = 1;
13+
14+
for (i = 0; i < m - 1; i++)
15+
h = (h * d) % q;
16+
17+
// Calculate hash value for pattern and text
18+
for (i = 0; i < m; i++) {
19+
p = (d * p + pattern.charAt(i)) % q;
20+
t = (d * t + txt.charAt(i)) % q;
21+
}
22+
23+
// Find the match
24+
for (i = 0; i <= n - m; i++) {
25+
if (p == t) {
26+
for (j = 0; j < m; j++) {
27+
if (txt.charAt(i + j) != pattern.charAt(j))
28+
break;
29+
}
30+
31+
if (j == m)
32+
System.out.println("Pattern is found at position: " + (i + 1));
33+
}
34+
35+
if (i < n - m) {
36+
t = (d * (t - txt.charAt(i) * h) + txt.charAt(i + m)) % q;
37+
if (t < 0)
38+
t = (t + q);
39+
}
40+
}
41+
}
42+
43+
public static void main(String[] args) {
44+
String txt = "ABCCDDAEFG";
45+
String pattern = "CDD";
46+
int q = 13;
47+
search(pattern, txt, q);
48+
}
49+
}

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.