leetcode 28. Implement strStr()
要理解next数组的构造思想，学习博客 http://www.cnblogs.com/yjiyjige/p/3263858.html。
13 ms 还有待提升 36%
public class Solution { public int[] getNext(String t){ int tlen = t.length(); int[] next = new int[tlen]; int k = -1; int j = 0; next[0] = -1; // j-->j+1 while(j<tlen-1){ if(k==-1||t.charAt(j)==t.charAt(k)){ next[++j] = ++k; }else{ k = next[k]; } } return next; } public int strStr(String s, String t) { if(s.equals(t)) return 0; if(s.equals("")) return -1; if(t.equals("")) return 0;//why? int slen = s.length(); int tlen = t.length(); int[] next = new int[tlen]; next = getNext(t); int i=0; int j=0; while(i<slen&&j<tlen){ while(i<slen&&j<tlen&&s.charAt(i)==t.charAt(j)){ i++; j++; } if(j<tlen){ if(next[j]==-1){ i++; j=0; }else{ j = next[j]; } }else{ return i-j; } } return -1; } }
