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

• 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;
}
}``````

• I think the time complexity is O(mn).

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