public String strStr(String haystack, String needle) {
        if(needle.isEmpty()) return haystack;
        int[] next = new int[needle.length()];
        buildNext(needle, next);
        int i = 0, j = 0;

        while(i < haystack.length()){
           if(j == -1 || haystack.charAt(i) == needle.charAt(j)){
               i++;
               j++;
           }else{
               j = next[j];
           }
           if(j == needle.length()) return haystack.substring(i - j);
        }
        return null;
    }