@Test public void randomTest() { int N = 300; Random r = new Random(); for (int i = 0; i < 1000; i++) { if (i % 100 == 9) N <<= 1; String text = RandomStringBuilder.randomStringBase62(N); if (r.nextBoolean()) { int st = r.nextInt(N / 2); String pattern = text.substring(st, st + 10); assertTrue(BoyerMoore.search(text, pattern) != -1); } else { String pattern = RandomStringBuilder.randomStringLowerCase(1 + r.nextInt(10)); System.out.println(expect(text,pattern)); assertEquals(expect(text,pattern), BoyerMoore.search(text, pattern)); } } }
public static int search(String text, String pattern) { char[] txt = text.toCharArray(); char[] pat = pattern.toCharArray(); int M = pat.length, N = txt.length; int[] right = new int[256]; Arrays.fill(right, -1); for (int i = 0; i < M; i++) { right[pat[i]] = i; } int skip; for (int i = 0; i <= N - M; i += skip) { skip = 0; for (int j = M - 1; j >= 0; j--) { if (pat[j] != txt[i + j]) { skip = Math.max(1, j - right[txt[i + j]]); break; } } if (skip == 0) return i; } return -1; }
BoyerMoore { public static int search(String text, String pattern) { char[] txt = text.toCharArray(); char[] pat = pattern.toCharArray(); int M = pat.length, N = txt.length; int[] right = new int[256]; Arrays.fill(right, -1); for (int i = 0; i < M; i++) { right[pat[i]] = i; } int skip; for (int i = 0; i <= N - M; i += skip) { skip = 0; for (int j = M - 1; j >= 0; j--) { if (pat[j] != txt[i + j]) { skip = Math.max(1, j - right[txt[i + j]]); break; } } if (skip == 0) return i; } return -1; } }
BoyerMoore { public static int search(String text, String pattern) { char[] txt = text.toCharArray(); char[] pat = pattern.toCharArray(); int M = pat.length, N = txt.length; int[] right = new int[256]; Arrays.fill(right, -1); for (int i = 0; i < M; i++) { right[pat[i]] = i; } int skip; for (int i = 0; i <= N - M; i += skip) { skip = 0; for (int j = M - 1; j >= 0; j--) { if (pat[j] != txt[i + j]) { skip = Math.max(1, j - right[txt[i + j]]); break; } } if (skip == 0) return i; } return -1; }  }
BoyerMoore { public static int search(String text, String pattern) { char[] txt = text.toCharArray(); char[] pat = pattern.toCharArray(); int M = pat.length, N = txt.length; int[] right = new int[256]; Arrays.fill(right, -1); for (int i = 0; i < M; i++) { right[pat[i]] = i; } int skip; for (int i = 0; i <= N - M; i += skip) { skip = 0; for (int j = M - 1; j >= 0; j--) { if (pat[j] != txt[i + j]) { skip = Math.max(1, j - right[txt[i + j]]); break; } } if (skip == 0) return i; } return -1; }  static int search(String text, String pattern); }
BoyerMoore { public static int search(String text, String pattern) { char[] txt = text.toCharArray(); char[] pat = pattern.toCharArray(); int M = pat.length, N = txt.length; int[] right = new int[256]; Arrays.fill(right, -1); for (int i = 0; i < M; i++) { right[pat[i]] = i; } int skip; for (int i = 0; i <= N - M; i += skip) { skip = 0; for (int j = M - 1; j >= 0; j--) { if (pat[j] != txt[i + j]) { skip = Math.max(1, j - right[txt[i + j]]); break; } } if (skip == 0) return i; } return -1; }  static int search(String text, String pattern);  }