@Test public void randomTest() { Random r = new Random(); for (int i = 100; i < 10000; i++) { int len = (int) Math.sqrt(i); String cur = RandomStringBuilder.randomStringLowerCase(len); StringBuilder sb = new StringBuilder(); int expect = 1 + r.nextInt(len - 1); for (int j = 0; j < r.nextInt(expect); j++) { if (r.nextBoolean()) sb.append(RandomStringBuilder.randomStringLowerCase(len)); else sb.append(cur); } sb.append(RandomStringBuilder.randomStringLowerCase(len)); for (int j = 0; j < expect; j++) sb.append(cur); sb.append(RandomStringBuilder.randomStringLowerCase(len)); for (int j = 0; j < r.nextInt(expect); j++) { if (r.nextBoolean()) sb.append(RandomStringBuilder.randomStringLowerCase(len)); else sb.append(cur); } Assert.assertEquals(expect, TandemRepeat.solve(cur, sb.toString())); } }
public static int solve(String pattern, String text) { int m = text.length(); int n = pattern.length(); if (n == 0) return -1; int k = m / n; if (k == 0) return 0; StringBuilder sb = new StringBuilder(); for (int i = 0; i < k; i++) { sb.append(pattern); } MyKMP kmp = new KMPplus(sb.toString()); kmp.search(text); return kmp.getMaxJ() / n; }
TandemRepeat { public static int solve(String pattern, String text) { int m = text.length(); int n = pattern.length(); if (n == 0) return -1; int k = m / n; if (k == 0) return 0; StringBuilder sb = new StringBuilder(); for (int i = 0; i < k; i++) { sb.append(pattern); } MyKMP kmp = new KMPplus(sb.toString()); kmp.search(text); return kmp.getMaxJ() / n; } }
TandemRepeat { public static int solve(String pattern, String text) { int m = text.length(); int n = pattern.length(); if (n == 0) return -1; int k = m / n; if (k == 0) return 0; StringBuilder sb = new StringBuilder(); for (int i = 0; i < k; i++) { sb.append(pattern); } MyKMP kmp = new KMPplus(sb.toString()); kmp.search(text); return kmp.getMaxJ() / n; }  }
TandemRepeat { public static int solve(String pattern, String text) { int m = text.length(); int n = pattern.length(); if (n == 0) return -1; int k = m / n; if (k == 0) return 0; StringBuilder sb = new StringBuilder(); for (int i = 0; i < k; i++) { sb.append(pattern); } MyKMP kmp = new KMPplus(sb.toString()); kmp.search(text); return kmp.getMaxJ() / n; }  static int solve(String pattern, String text); }
TandemRepeat { public static int solve(String pattern, String text) { int m = text.length(); int n = pattern.length(); if (n == 0) return -1; int k = m / n; if (k == 0) return 0; StringBuilder sb = new StringBuilder(); for (int i = 0; i < k; i++) { sb.append(pattern); } MyKMP kmp = new KMPplus(sb.toString()); kmp.search(text); return kmp.getMaxJ() / n; }  static int solve(String pattern, String text);  }