题目：
实现 strStr() 函数
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll" 输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba" 输出: -1
解题：
python 里面有个find()函数，可以直接查找匹配的字符串，并返回索引，这边不用这种方法。
方法一：暴力匹配算法
class Solution: def strStr(self, haystack: str, needle: str) -> int: hlen = len(haystack) nlen = len(needle) i,j = 0,0 while i<hlen and j<nlen: if haystack[i]==needle[j]: i+=1 j+=1 else: i = i-j+1 j=0 if j == nlen: return i-j else: return -1
方法二：KMP算法
KMP算法相比暴力匹配算法改进了什么呢？
它创建了Next数组，再遍历一遍需要被匹配的字符串，所以时间复杂度为O(m+n),而暴力匹配算法时间复杂度为O(mn)。
暴力匹配算法，在每次匹配结束后，被匹配的字符串索引需要i = i-j+1 回溯，匹配的模板字符串需要变成j=0,然而，有了KMP算法，被匹配的字符串，索引不需要回溯，匹配的模板字符串索引也不用j=0开始，
这样子在字符串匹配过程中时间复杂度为O(n)，创建next列表时 时间复杂度为O(m)，总共时间复杂度为O(m+n)。
python解法
class Solution: def strStr(self, haystack: str, needle: str) -> int: m = len(needle) index = 0 i = 1 pnext = [0]*m while i<m: if needle[index]==needle[i]: pnext[i]=index+1 i+=1 index+=1 elif index!=0: index = pnext[index-1] else: i+=1 m = len(needle) n = len(haystack) i,j = 0,0 while i<m and j<n: if needle[i]==haystack[j]: i+=1 j+=1 elif i!=0: i = pnext[i-1] else: j+=1 if i==m: return j-i else: return -1
说一下创建next过程
可能index = pnext[index-1]会有所疑惑，这一步骤是为了获得上一个字母已经匹配到字符串的索引（这样就不需要回溯i了,index也不需要归为0，然后重新开始匹配了(虽然只是在创建next，但已经用到了KMP的核心思想了)）
比如:
haystack = "aaaaabbabbbaaabb" needle = "bbaaaaabbabbb" >>[0, 1, 0, 0, 0, 0, 0, 1, 2, 3, 1, 2, 2] #得到的pnext
可以看到每次并不都是0、1、2、3…这样开始。正是因为每次不是这样开始，才使得该算法效率高。
当index=2，i为最后那个“b”的索引时候，发现pnext[index]!=pnext[i]，于是index = pnext[index-1]得到的index=1,发现pnext[index]==pnext[i],于是pnext[i]=index+1为2，所以pnext最后一个值为2。
可以发现：
创建next过程中，是字符串后面部分和前面部分匹配，而两个字符串匹配时候，是两个串之间比。
c++解法
class Solution { public: vector<int> create_pnext(string needle){ int m=needle.size(); int index=0; int i=1; vector<int> pnext(m); while(i<m){ if(needle[index]==needle[i]){ pnext[i]=index+1; index++; i++; } else if(index!=0){ index=pnext[index-1]; } else{ i++; } } return pnext; } int strStr(string haystack, string needle) { vector<int> pnext=create_pnext(needle); int m=haystack.size(); int n=needle.size(); int i=0,j=0; while(i<m&&j<n){ if(haystack[i]==needle[j]){ i++; j++; } else if(j!=0){ j=pnext[j-1]; } else{ i++; } } if(j==n) return i-j; return -1; } };
方法三：内置函数
c++解法
class Solution { public: int strStr(string haystack, string needle) { if(needle.empty()) return 0; int pos=haystack.find(needle); if(pos==-1) return -1; return pos; } };
