NOT KMP O(n) Algorithm Come up by myself (Java Solution)


  • 0
    S

    I use one pointer p for haystack, two pointers i and j for needle. First compare haystack.charAt(p) with needle.charAt(i) and keep increase index if matches, and search for match start in the middle by using j. When needle.charAt(i) fails, directly turn to j, keep comparing haystack.charAt(p) and needle.charAt(j).

    Key point is marking the possible match that start in the middle, once one index fails, turn to the other index.

    The code is not clear enough yet.

    public class Solution {
        public int strStr(String haystack, String needle) {
            int p = 0; // for haystack
            int i = 0, j = 0; // for needle
            int state = 0; // state=0 means i being compared, state=1 means j is being compared
            while(p < haystack.length() && i < needle.length() && j < needle.length()){
                switch(state){
                    case 0:
                        if(i!= 0){
                            // if a new match start in the middle
                            if(haystack.charAt(p)==needle.charAt(j))
                                j++;
                            else if(haystack.charAt(p)==needle.charAt(0))
                            	j = 1;
                            else
                            	j = 0;
                        }
                        if(haystack.charAt(p)==needle.charAt(i)){
                            i++;
                        }else{
                            i = 0;
                            state = 1;
                        }
                        break;
                    case 1:
                        if(j!=0){
                            // if a new match start in the middle
                            if(haystack.charAt(p)==needle.charAt(i))
                                i++;
                            else if(haystack.charAt(p)==needle.charAt(0))
                            	i = 1;
                            else
                            	i = 0;
                        }
                        if(haystack.charAt(p)==needle.charAt(j)){
                            j++;
                        }else{
                            j = 0;
                            state = 0;
                        }
                        break;
                    default:
                        break;
                }
                p++;
                // if a total match is caught
                if(i==needle.length() || j==needle.length())
                    return p-needle.length();
            }
            return needle.length()==0?0:-1;
        }
    }

  • 0
    Q

    I think the time complexity is O(mn).


Log in to reply
 

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