|
|
back to boardJava AC 3rd place solution Posted by esbybb 9 Aug 2015 23:39 //package timus; import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.io.Reader; import java.util.StringTokenizer; public class p1423 { static char[] t; static char[] p; static int[] pi; static int N; public static void main(String[] args) throws FileNotFoundException { InputStream is = System.in; FastScanner sc = new FastScanner(new InputStreamReader(is)); N = sc.nextInt(); String tt = sc.next(); tt += tt; t = tt.toCharArray(); p = sc.next().toCharArray(); pi = new int[N]; System.out.println(KMPMatcher()); } static int KMPMatcher() { computePrefixFunction(); int equals = 0; for (int i = 0; i < N + N; i++) { while (equals > 0 && p[equals] != t[i]) equals = pi[equals - 1]; if (p[equals] == t[i]) equals++; if (equals == N) { if (i == N - 1) { return 0; } else { return N + N - (i + 1); } } } return -1; } static void computePrefixFunction() { int k = 0; for (int q = 1; q < N; q++) { while (k > 0 && p[k] != p[q]) k = pi[k - 1]; if (p[k] == p[q]) k++; pi[q] = k; } } static class FastScanner { BufferedReader br; StringTokenizer st; FastScanner(Reader in) { br = new BufferedReader(in); } String next() { while (st == null || !st.hasMoreTokens()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } } } |
|
|