链接：实现 strStr()

字符串查找，在text中查找pattern第一次出现的位置。暴力解法使用双重循环，复杂度。高效解法有KMP算法，时间复杂度为。

最长相同前后缀

对于字符abcd，它的前缀有a、ab、abc，它的后缀有d、cd、bcd。在给定前、后缀长度的情况下，前缀、后缀字符串是确定的。如果前缀字符串等于后缀字符串，将这种情况叫做相同前后缀。在所有相同前后缀字符串中，长度最长的叫做最长相同前后缀。

1. pattern = "a" ， 没有前后缀，长度为0或者1的字符串没有前缀或后缀
2. pattern = "abcda" ， 相同前后缀有"a"，最长相同前后缀为"a"
3. pattern = "aacaa" ， 相同前后缀有"a"、"aa"，最长相同前后缀为"aa"
4. pattern = "abcabca" ， 相同前后缀有"a"、"abca"，最长相同前后缀为"abca"

前后缀长度数组（next数组）

对于一个给定的字符串pattern（长度为）,对于pattern的每个字串pattern[0:i]，计算出每个字串的最长相同前后缀的长度，由此构成的数组为前后缀长度数组，也就是next数组。

pattern = "abcaabca"

1. i = 0 ， 子串为"a"， 没有前后缀，next[0]=0
2. i = 1 ， 子串为"ab"，没有相同前后缀， next[1] = 0
3. i = 2 ， 子串为"abc"， 没有相同前后缀，next[2] = 0
4. i = 3 ， 子串为"abca"，最长相同前后缀为"a"，next[3] = 1
5. i = 4 ， 子串为"abcaa"， 最长相同前后缀为"a"， next[4] = 1
6. i = 5 ， 子串为"abcaab"， 最长相同前后缀为"ab"，next[5] = 2
7. i = 6 ， 子串为"abcaabc"，最长相同前后缀为"abc"，next[6] = 3
8. 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