@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); KMP dfa = new KMP(pattern); KMPplus nfa = new KMPplus(pattern); assertTrue(dfa.search(text) != -1); assertTrue(nfa.search(text) != -1); } else { String pattern = RandomStringBuilder.randomStringLowerCase(1 + r.nextInt(10)); KMP dfa = new KMP(pattern); KMPplus nfa = new KMPplus(pattern); System.out.println(expect(text,pattern)); assertEquals(expect(text,pattern), dfa.search(text)); assertEquals(dfa.search(text), nfa.search(text)); } } }
public int search(String text) { maxJ = 0; char[] txt = text.toCharArray(); int j = 0, i; for (i = 0; i < txt.length && j < pat.length; i++) { j = dfa[txt[i] - basePos][j]; maxJ = Math.max(j, maxJ); } if (j == pat.length) return i - j; return -1; }
KMP implements MyKMP { public int search(String text) { maxJ = 0; char[] txt = text.toCharArray(); int j = 0, i; for (i = 0; i < txt.length && j < pat.length; i++) { j = dfa[txt[i] - basePos][j]; maxJ = Math.max(j, maxJ); } if (j == pat.length) return i - j; return -1; } }
KMP implements MyKMP { public int search(String text) { maxJ = 0; char[] txt = text.toCharArray(); int j = 0, i; for (i = 0; i < txt.length && j < pat.length; i++) { j = dfa[txt[i] - basePos][j]; maxJ = Math.max(j, maxJ); } if (j == pat.length) return i - j; return -1; } KMP(String pattern);  KMP(String pattern, int R, int base); }
KMP implements MyKMP { public int search(String text) { maxJ = 0; char[] txt = text.toCharArray(); int j = 0, i; for (i = 0; i < txt.length && j < pat.length; i++) { j = dfa[txt[i] - basePos][j]; maxJ = Math.max(j, maxJ); } if (j == pat.length) return i - j; return -1; } KMP(String pattern);  KMP(String pattern, int R, int base); int search(String text); int getMaxJ(); }
KMP implements MyKMP { public int search(String text) { maxJ = 0; char[] txt = text.toCharArray(); int j = 0, i; for (i = 0; i < txt.length && j < pat.length; i++) { j = dfa[txt[i] - basePos][j]; maxJ = Math.max(j, maxJ); } if (j == pat.length) return i - j; return -1; } KMP(String pattern);  KMP(String pattern, int R, int base); int search(String text); int getMaxJ();  }