public class Solution { public String strStr(String haystack, String needle) { if(haystack==null || needle == null || needle.length()==0) return haystack; if(needle.length()>haystack.length()) return null; char[] a = haystack.toCharArray(); char[] b = needle.toCharArray(); int[] next = getNextArray(b); int i = 0,j = 0; while (i < a.length) { while (j >= 0 && a[i] != b[j]) { j = next[j]; } i++; j++; if (j == b.length) { return haystack.substring(i - b.length); } } return null; } private int[] getNextArray(char[] s){ if(s.length==1) return new int[]{-1}; int[] next = new int[s.length]; next[0] = -1; next[1] = 0; int pos = 2; int cn = 0; while(pos0) cn = next[cn]; else next[pos++] = 0; } return next; } }