Super Slow AC KMP solution just for FUN.


  • 0
    Z
        public int strStr(String haystack, String needle) {
            if(needle.length()==0)return 0;
            int[][] T = new int[128][needle.length()];
            int last = 0;
            for(int cur=0;cur<T[0].length;cur++){
                for(int j = 0;j<128;j++){
                    if((char)j==needle.charAt(cur))T[j][cur] = cur+1;
                    else{
                        if(cur==0)T[j][cur]=0;
                        else T[j][cur] = T[j][last];
                        }
                }
                last = cur==0?0:T[needle.charAt(cur)][last];
            }
            //start autometa
            int curstat = 0;
            boolean hit = false;
            int i = 0;
            for(;i<haystack.length();i++){
                curstat = T[haystack.charAt(i)][curstat];
                if(curstat==needle.length()){hit = true;break;}
            }
            if(!hit)return -1;
            return i - needle.length()+1;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.