Q28 Implement strStr()

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

解题思路:

此题即实现Python中内置函数 find() 的功能。简单方法就是逐个字符比较，当匹配失效后，将子串重新移到开始位置，主串回退前面已经匹配的n个字符，然后继续比较。时间复杂度 O(m*n)

注意点:

此题可采用 KMP 算法求解，时间复杂度可以降为 O(m+n)，后续补充。

Python实现：

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个字符
                count = 0
            i += 1  
            if count == needlen:
                return i - count
        return -1

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