KarpRabin code

kunal-kushwaha · web-flow · commit 5c45a424d633 · 2023-10-29T21:31:43.000Z
diff --git a/lectures/25-hashmaps/code/KarpRabin/KarpRabin.java b/lectures/25-hashmaps/code/KarpRabin/KarpRabin.java
@@ -0,0 +1,35 @@
+public class KarpRabin {
+  private final int PRIME = 101;
+
+  private double calculateHash(String str) {
+    double hash = 0;
+    for(int i=0; i < str.length(); i++) {
+      hash += str.charAt(i) * Math.pow(PRIME, i);
+    }
+    return hash;
+  }
+
+  private double updateHash(double prevHash, char oldChar, char newChar, int patternLength) {
+      double newHash = (prevHash - oldChar) / PRIME;
+    newHash = newHash + newChar * Math.pow(PRIME, patternLength - 1);
+    return newHash;
+  }
+
+  public void search(String text, String pattern) {
+    int patternLength = pattern.length();
+      double patternHash = calculateHash(pattern);
+      double textHash = calculateHash(text.substring(0, patternLength));
+
+    for(int i=0; i<= text.length() - patternLength; i++) {
+      if(textHash == patternHash) {
+        if(text.substring(i, i+patternLength).equals(pattern)) {
+          System.out.println("Pattern found at index " + i);
+        }
+      }
+
+      if (i < text.length() - patternLength) {
+        textHash = updateHash(textHash, text.charAt(i), text.charAt(i + patternLength), patternLength);
+      }
+    }
+  }
+}
diff --git a/lectures/25-hashmaps/code/KarpRabin/Main.java b/lectures/25-hashmaps/code/KarpRabin/Main.java
@@ -0,0 +1,6 @@
+class Main {
+  public static void main(String[] args) {
+    KarpRabin algo = new KarpRabin();
+    algo.search("ApoorvKunalRahul", "Kunal");
+  }
+}
