|  | 
|  | 
| вернуться в форум | Java AC 3rd place solution Послано esbybb  9 авг 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());
 }
 }
 }
 | 
 | 
|