```
public class Solution {
public String strStr(String haystack, String needle)
{
if(haystack== null) return null;
if(needle==null || needle.length()==0) return haystack;
if(needle.length()>haystack.length()) return null;
int pat_length = needle.length();
int right[] = new int[256];
for(int i=0;i<256;i++)
right[i] =-1;
for(int i=0;i<pat_length;i++)
right[needle.charAt(i)] =i;
int rtn = search(right,haystack,needle);
if(rtn == haystack.length()) return null;
else
return haystack.substring(rtn);
}
public int search(int[] right, String haystack,String needle)
{
int M = haystack.length();
int N = needle.length();
int i,j;
int skip =0;
for(i=0; i<=M-N; i+=skip)
{
skip =0;
for(j=N-1;j>=0;j--)
{
if(needle.charAt(j)!=haystack.charAt(i+j))
{
skip = j-right[haystack.charAt(j+i)];
if(skip<=0) skip=1;
break;
}
}
if(skip ==0) return i;
}
return M;
}
```

}

- I tried DFA version of KMP, it turned out that it exceeds the time limit. I went back to the Algorithm book and checked time complexity of KMP(DFA version). Surprisingly, the typical runtime of KMP is same as brute force, which is 1.1N. It only improves the worst case runtime from NM to 2N. This is why leetcode accepts the brute force.
- The Boyer-Moore algorithm only needs O(N/M) for average runtime and O(NM) for worst case.

Hope this helps. : )