/**
 * @author Roderland
 * @since 1.0
 */
public class KMP {
 public static void main(String[] args) {
 String s = "aaaaaaab";
 String p = "aaab";
 System.out.println(new KMP().kmp(s, p));
 }
 public int kmp(String s, String p) {
 if (s==null || p==null || s.length()==0 || p.length()==0) return -1;
 if (p.length()>s.length()) return kmp(p, s);
 int[] next = getPrefix(p);
 int x = 0;
 int y = 0;
 while (x<s.length() && y<p.length()) {
 if (s.charAt(x)==p.charAt(y)) {
 x++;
 y++;
 } else {
 if (y==0) x++;
 else y=next[y-1];
 }
 }
 return y >= p.length()?x-p.length():-1;
 }

 private int[] getPrefix(String p) {
 int[] res = new int[p.length()-1];
 res[0]=0;
 for (int i = 1; i < res.length; i++) {
 if (p.charAt(i)==p.charAt(res[i-1])) res[i]=res[i-1]+1;
 else res[i]=0;
 }
 return res;
 }
}