Implement strStr()

To get accepted is not difficult, it might be due to the time limit is not strict, i.e. O(n * m) can be tolerated in OJ. Since I misunderstood this question, and always failed in one test case, I googled this question, and found very good solution, which takes O(n), called as rolling hash. Basic idea of this algorithm is to hash each segment of haystack, the length is same as needle, and then compare the code with that of needle. The tricky part might be how to implement hash function. BTW, KMP algorithm is reviewed when dealing with this question, good thing.

It is good to find other's blog, by Code_Ganker , where solutions to 151 questions in LeetCode are posted. This is really helpful. Thanks Code_Ganker for his or her post.

//Solution 1 is my code, O(n * m), brute force, lol
public class Solution {
    public String strStr(String haystack, String needle) {
       
        if(haystack == null || needle == null || haystack.length() < needle.length()){
            return null;
        }
        int nLen = needle.length();
        if (nLen == 0) return haystack;
        for(int i = 0; i <= haystack.length() - nLen; i ++){
            if(haystack.substring(i,nLen+i).equals(needle)) return haystack.substring(i);
        }
        return null;
    }
}

Solution 2, contributed by Code_Ganker, O(n): please check this url out :
http://blog.csdn.net/linhuanmars/article/details/20276833