@Test public void testIndexOfRabinKarp() throws Exception { assertEquals(0, indexOfRabinKarp("abc", "a")); assertEquals(0, indexOfRabinKarp("abc", "abc")); assertEquals(1, indexOfRabinKarp("abc", "b")); assertEquals(1, indexOfRabinKarp("abc", "bc")); assertEquals(2, indexOfRabinKarp("abc", "c")); assertEquals(-1, indexOfRabinKarp("abc", "d")); assertEquals(0, indexOfRabinKarp("abc", "")); assertEquals(1, indexOfRabinKarp("abababababab", "bababab")); assertEquals(7, indexOfRabinKarp("abcdefghjklmopqrstvuwxyz", "hjklmopqrstvuw")); }
static int indexOfRabinKarp(@Nonnull String text, @Nonnull String pattern) { final int m = pattern.length(); final int n = text.length(); if (n < m) { return -1; } if(m == 0) { return 0; } final long q = 19999999991L; final long d = 100; long h = 1; for (int i = 0; i < m - 1; i++) { h = (h * d) % q; } long t = 0; long p = 0; for (int i = 0; i < m; i++) { t = (d * t + text.charAt(i)) % q; p = (d * p + pattern.charAt(i)) % q; } for (int i = 0; i < n - m + 1; i++) { if (t == p) { if (text.startsWith(pattern, i)) { return i; } } if (i < n - m) { final char leftChar = text.charAt(i); final char rightChar = text.charAt(i + m); t = (d * (t - h * leftChar) + rightChar) % q; } } return -1; }
Strings { static int indexOfRabinKarp(@Nonnull String text, @Nonnull String pattern) { final int m = pattern.length(); final int n = text.length(); if (n < m) { return -1; } if(m == 0) { return 0; } final long q = 19999999991L; final long d = 100; long h = 1; for (int i = 0; i < m - 1; i++) { h = (h * d) % q; } long t = 0; long p = 0; for (int i = 0; i < m; i++) { t = (d * t + text.charAt(i)) % q; p = (d * p + pattern.charAt(i)) % q; } for (int i = 0; i < n - m + 1; i++) { if (t == p) { if (text.startsWith(pattern, i)) { return i; } } if (i < n - m) { final char leftChar = text.charAt(i); final char rightChar = text.charAt(i + m); t = (d * (t - h * leftChar) + rightChar) % q; } } return -1; } }
Strings { static int indexOfRabinKarp(@Nonnull String text, @Nonnull String pattern) { final int m = pattern.length(); final int n = text.length(); if (n < m) { return -1; } if(m == 0) { return 0; } final long q = 19999999991L; final long d = 100; long h = 1; for (int i = 0; i < m - 1; i++) { h = (h * d) % q; } long t = 0; long p = 0; for (int i = 0; i < m; i++) { t = (d * t + text.charAt(i)) % q; p = (d * p + pattern.charAt(i)) % q; } for (int i = 0; i < n - m + 1; i++) { if (t == p) { if (text.startsWith(pattern, i)) { return i; } } if (i < n - m) { final char leftChar = text.charAt(i); final char rightChar = text.charAt(i + m); t = (d * (t - h * leftChar) + rightChar) % q; } } return -1; } protected  Strings(); }
Strings { static int indexOfRabinKarp(@Nonnull String text, @Nonnull String pattern) { final int m = pattern.length(); final int n = text.length(); if (n < m) { return -1; } if(m == 0) { return 0; } final long q = 19999999991L; final long d = 100; long h = 1; for (int i = 0; i < m - 1; i++) { h = (h * d) % q; } long t = 0; long p = 0; for (int i = 0; i < m; i++) { t = (d * t + text.charAt(i)) % q; p = (d * p + pattern.charAt(i)) % q; } for (int i = 0; i < n - m + 1; i++) { if (t == p) { if (text.startsWith(pattern, i)) { return i; } } if (i < n - m) { final char leftChar = text.charAt(i); final char rightChar = text.charAt(i + m); t = (d * (t - h * leftChar) + rightChar) % q; } } return -1; } protected  Strings(); static String[] split(String source, String subString); static String convertStream(InputStream in); static boolean notEmpty(@Nullable String s); static boolean isEmpty(@Nullable CharSequence s); @Nonnull static String getNotEmpty(@Nullable CharSequence s, @Nonnull String defaultValue); @Nonnull static String getNotEmpty(@Nullable T t, @Nonnull String defaultValue); static String[] toString(@Nonnull Enum... enums); @Nonnull static Character[] toObjects(char[] array); @Nonnull static String fromStackTrace(@Nullable StackTraceElement... stackTraceElements); @Nonnull static String repeat(@Nonnull String str, int repeat); @Nonnull static String repeat(char ch, int repeat); @Nonnull static String generateRandomString(int length); @Nonnull static String toHex(@Nonnull String s); @Nonnull static String fromHex(@Nonnull CharSequence hex); @Nonnull static String getAllEnumValues(@Nonnull Class<? extends Enum> enumClass); @Nonnull static String getAllValues(@Nonnull List<?> elements); @Nonnull static String toHtml(@Nonnull CharSequence text); }
Strings { static int indexOfRabinKarp(@Nonnull String text, @Nonnull String pattern) { final int m = pattern.length(); final int n = text.length(); if (n < m) { return -1; } if(m == 0) { return 0; } final long q = 19999999991L; final long d = 100; long h = 1; for (int i = 0; i < m - 1; i++) { h = (h * d) % q; } long t = 0; long p = 0; for (int i = 0; i < m; i++) { t = (d * t + text.charAt(i)) % q; p = (d * p + pattern.charAt(i)) % q; } for (int i = 0; i < n - m + 1; i++) { if (t == p) { if (text.startsWith(pattern, i)) { return i; } } if (i < n - m) { final char leftChar = text.charAt(i); final char rightChar = text.charAt(i + m); t = (d * (t - h * leftChar) + rightChar) % q; } } return -1; } protected  Strings(); static String[] split(String source, String subString); static String convertStream(InputStream in); static boolean notEmpty(@Nullable String s); static boolean isEmpty(@Nullable CharSequence s); @Nonnull static String getNotEmpty(@Nullable CharSequence s, @Nonnull String defaultValue); @Nonnull static String getNotEmpty(@Nullable T t, @Nonnull String defaultValue); static String[] toString(@Nonnull Enum... enums); @Nonnull static Character[] toObjects(char[] array); @Nonnull static String fromStackTrace(@Nullable StackTraceElement... stackTraceElements); @Nonnull static String repeat(@Nonnull String str, int repeat); @Nonnull static String repeat(char ch, int repeat); @Nonnull static String generateRandomString(int length); @Nonnull static String toHex(@Nonnull String s); @Nonnull static String fromHex(@Nonnull CharSequence hex); @Nonnull static String getAllEnumValues(@Nonnull Class<? extends Enum> enumClass); @Nonnull static String getAllValues(@Nonnull List<?> elements); @Nonnull static String toHtml(@Nonnull CharSequence text); static final String LINE_SEPARATOR; static final Character[] EMPTY_CHARACTER_OBJECT_ARRAY; }