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
