Skip to content

Instantly share code, notes, and snippets.

@RitamChakraborty
Created August 11, 2019 18:19
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save RitamChakraborty/bd114a2201a2faff2e25905eec2f6b3b to your computer and use it in GitHub Desktop.
Save RitamChakraborty/bd114a2201a2faff2e25905eec2f6b3b to your computer and use it in GitHub Desktop.
Rabin-Karp string matching algorithm in java
public class RabinKarpAlgorithm {
private static long getNumber(char[] chars) {
long number = 0;
for (char ch: chars) {
number = (number * 10) + ((int) ch - (int)'a' + 1);
}
return number;
}
private static boolean contains(String a, String b) {
String smaller = a.length() <= b.length() ? a : b;
String larger = a.length() > b.length() ? a : b;
char[] ch1 = larger.toCharArray();
char[] ch2 = smaller.toCharArray();
long smallerNumber = getNumber(ch2);
int i = 0;
int j = smaller.length() - 1;
long number = 0;
while (true) {
if (i == 0) {
for (int k = 0; k <= j; k++) {
number = (number * 10) + ((int) ch1[k] - (int)'a' + 1);
}
}
if (number == smallerNumber) {
return true;
} else {
j++;
if (j == ch1.length) {
break;
} else {
number = ((number - ((int) ch1[i] - (int) 'a' + 1) * (long) Math.pow(10, ch2.length - 1)) * 10) + ((int) ch1[j] - (int) 'a' + 1);
i++;
}
}
}
return false;
}
public static void main(String[] args) {
String a = "abcdeabdeabcdf";
String b = "abcdf";
System.out.println(contains(a, b));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment