Last active
February 22, 2021 07:06
-
-
Save CaffeineShawn/707cf1588a7afa8084d18f715a6bc270 to your computer and use it in GitHub Desktop.
Rabin Karp Algorithm Completed
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package com.company; | |
| import java.io.OutputStream; | |
| import java.lang.ref.SoftReference; | |
| import java.util.*; | |
| public class Main { | |
| public static void main(String[] args) { | |
| Solution solution = new Solution(); | |
| String haystack = "ababaabbbbababbaabaaabaabbaaaabbabaabbbbbbabbaabbabbbabbbbbaaabaababbbaabbbabbbaabbbbaaabbababbabbbabaaabbaabbabababbbaaaaaaababbabaababaabbbbaaabbbabb"; | |
| String needle = "abbabbbabaa"; | |
| System.out.println(solution.strStr(haystack, needle)); | |
| } | |
| } | |
| class Solution { | |
| public int strStr(String haystack, String needle) { | |
| double hashHayStack = Hash(haystack); | |
| double hashNeedle = Hash(needle); | |
| double curHash = 0; | |
| boolean matched = true; | |
| if ((haystack.length() == 0 && needle.length() > 0) || haystack.length() < needle.length()) { | |
| System.out.println("Aborted"); | |
| return -1; | |
| } | |
| // System.out.println(Hash(needle) + " needleHash"); | |
| int m = haystack.length(), n = needle.length(); | |
| curHash = Hash(haystack.substring(0, n)); | |
| // System.out.println(curHash + " initialHash" + Hash("ab")); | |
| for (int i = 0; i < m - n + 1; i++) { | |
| if (i > 0){ | |
| curHash = hashRecalculate(curHash, n, haystack, i); | |
| System.out.println(curHash + " recalculatedHash " + i); | |
| } | |
| if(curHash == hashNeedle) { | |
| for (int j = 0; j < n; j++) { | |
| if (needle.charAt(j) != haystack.charAt(i + j)) { | |
| matched = false; | |
| break; | |
| } | |
| } | |
| System.out.println(matched); | |
| if(matched) return i; | |
| } | |
| } | |
| return -1; | |
| } | |
| static int prime = 3; | |
| // If prime equals to 101 as said in the video, when the string is getting much larger the result of the hash function will exceed its limit, and we won't get a possible match. | |
| private double Hash(String s) { | |
| // System.out.println(s); | |
| double res = 0; | |
| for (int i = 0; i < s.length(); i++) { | |
| res += (s.charAt(i) - 'a') * Math.pow(prime,i); | |
| } | |
| return res; | |
| } | |
| private double hashRecalculate(double curHash, int len, String s, int start) { | |
| curHash -= s.charAt(start - 1) - 'a'; | |
| curHash /= prime; | |
| curHash += (s.charAt(start - 1 + len) - 'a') * Math.pow(prime, len - 1); | |
| return curHash; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment