Java 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());
}
}
}