Implement strStr()

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Update (2014-11-02):
The signature of the function had been updated to return the index instead of the pointer. If you still see your function signature returns a char * or String, please click the reload button  to reset your code definition.

Solutio1: brute force 

判断一个字符串是否是另一个字符串的子串。
经典的算法是KMP算法，Knuth–Morris–Pratt algorithm。KMP算法是最优的线性算法，复杂度已经达到这个问题的下限，但是比较复杂。

brute force的算法，假设原串的长度是n，匹配串的长度是m。

对原串的每一个长度为m的字串都判断是否跟匹配串一致。总共有n-m+1个子串，

所以算法时间复杂度为O((n-m+1)*m)=O(n*m)，空间复杂度是O(1)。

public class Solution {
    public int strStr(String haystack, String needle) {
        if(haystack == null || needle == null || needle.length() == 0) {
            return 0;
        }
        if(haystack.length() < needle.length()) {
            return -1;
        }
        
        for(int i = 0; i <= haystack.length() - needle.length(); i++) {
            Boolean hasStr = true;
            for (int j = 0; j < needle.length(); j++) {
                if(needle.charAt(j) != haystack.charAt(i + j)) {
                    hasStr = false;
                    break;
                }
            }
            if(hasStr) {
                return i;
            }
        }
        return -1;
    }
}

或者

public class Solution {
    public int strStr(String haystack, String needle) {
        for(int i = 0; ; i++) {
            for(int j = 0; ; j++) {
                if(j == needle.length()) 
                    return i;
                
                if(i + j == haystack.length())
                    return -1;
                
                if(needle.charAt(j) != haystack.charAt(i + j))
                    break;
            }
        }
    }
}

Reference (rolling hash): http://blog.csdn.net/linhuanmars/article/details/20276833