Implement strStr().

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

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

解題思路:

此題即實(shí)現(xiàn)Python中內(nèi)置函數(shù) find() 的功能。簡(jiǎn)單方法就是逐個(gè)字符比較，當(dāng)匹配失效后，將子串重新移到開始位置，主串回退前面已經(jīng)匹配的n個(gè)字符，然后繼續(xù)比較。時(shí)間復(fù)雜度 O(m*n)

注意點(diǎn):

此題可采用 KMP 算法求解，時(shí)間復(fù)雜度可以降為 O(m+n)，后續(xù)補(bǔ)充。

Python實(shí)現(xiàn)：

class Solution:
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        haylen = len(haystack)
        needlen = len(needle)
        if needlen == 0:
            return 0
        if haylen < needlen:
            return -1
        i = 0; j = 0; count = 0;
        while i < haylen:
            if j < needlen and haystack[i] == needle[j]:
                j += 1
                count += 1
            elif count > 0 and haystack[i] != needle[j]:  # needle從頭開始比較
                j = 0  
                i -= count  # 回退count個(gè)字符
                count = 0
            i += 1  
            if count == needlen:
                return i - count
        return -1

a = "ississip"
b = "issip"
c = Solution()
print(c.strStr(a,b))  # 3