链接：实现 strStr()
字符串查找，在text中查找pattern第一次出现的位置。暴力解法使用双重循环，复杂度。高效解法有KMP算法，时间复杂度为
。
最长相同前后缀
对于字符abcd，它的前缀有a、ab、abc，它的后缀有d、cd、bcd。在给定前、后缀长度的情况下，前缀、后缀字符串是确定的。如果前缀字符串等于后缀字符串，将这种情况叫做相同前后缀。在所有相同前后缀字符串中，长度最长的叫做最长相同前后缀。
- pattern = "a" ， 没有前后缀，长度为0或者1的字符串没有前缀或后缀
- pattern = "abcda" ， 相同前后缀有"a"，最长相同前后缀为"a"
- pattern = "aacaa" ， 相同前后缀有"a"、"aa"，最长相同前后缀为"aa"
- pattern = "abcabca" ， 相同前后缀有"a"、"abca"，最长相同前后缀为"abca"
前后缀长度数组（next数组）
对于一个给定的字符串pattern（长度为）,对于pattern的每个字串pattern[0:i]，计算出每个字串的最长相同前后缀的长度，由此构成的数组为前后缀长度数组，也就是next数组。
pattern = "abcaabca"
- i = 0 ， 子串为"a"， 没有前后缀，next[0]=0
- i = 1 ， 子串为"ab"，没有相同前后缀， next[1] = 0
- i = 2 ， 子串为"abc"， 没有相同前后缀，next[2] = 0
- i = 3 ， 子串为"abca"，最长相同前后缀为"a"，next[3] = 1
- i = 4 ， 子串为"abcaa"， 最长相同前后缀为"a"， next[4] = 1
- i = 5 ， 子串为"abcaab"， 最长相同前后缀为"ab"，next[5] = 2
- i = 6 ， 子串为"abcaabc"，最长相同前后缀为"abc"，next[6] = 3
- i = 7 ， 子串为"abcaabca"，最长相同前后缀为"abca"，next[7] = 4
这里我们通过设置不同的前后缀长度，来找到每个字串的最长相同前缀长度，形成next数组。按照这个设置不同前后缀长度，产生前后缀，并确认是否相同的方法，计算next数组的复杂度为，实际上，next数组能在
的时间复杂度内计算出来。
在介绍如何快速计算next数组前，我们先看看如何利用next数组来快速在text中找到pattern，这个快速查找的技巧也会用在快速计算next数组中。
假设text="abcabcabf"，pattern="abcabf"，进行字符串匹配，表示text的下标，
表示pattern的下标。刚开始
，我们很容易将text[0:4]与pattern[0:4]对应上，但是对比text[5]和pattern[5]时，由于"c"不等于"f"，所以这次匹配失败了。
但是我们不用在把设置为1，
设置为0，进行暴力匹配。我们可以保持当前的
"c"不变，将
设置为2，继续比较text[5]和pattern[2]。
这是因为pattern[0:4]的最长相同前后缀为"ab"，所以pattern[0:1]=pattern[3:4]="ab"，而由于text[0:4]与pattern[0:4]时匹配的，所以有text[0:1]=text[3:4]="ab"，所以就有text[3:4]=pattern[0:1]，然后就是将继续向后遍历对比，刚好可以完全匹配pattern。
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
m = len(haystack)
n = len(needle)
next = self.get_next_array(needle)
j = 0
for i in range(m):
while j > 0 and haystack[i] != needle[j]:
j = next[j-1]
if haystack[i] == needle[j]:
j += 1
if j == n:
return i - n +1
else:
return -1
def get_next_array(self, needle):
n = len(needle)
res = [0] * n
j = 0
for i in range(1, n):
while j > 0 and needle[i] != needle[j]:
j = res[j-1]
if needle[i] == needle[j]:
j += 1
res[i] = j
return res
