鏈接：實(shí)現(xiàn) strStr()

字符串查找，在text中查找pattern第一次出現(xiàn)的位置。暴力解法使用雙重循環(huán)，復(fù)雜度。高效解法有KMP算法，時(shí)間復(fù)雜度為。

最長(zhǎng)相同前后綴

對(duì)于字符abcd，它的前綴有a、ab、abc，它的后綴有d、cd、bcd。在給定前、后綴長(zhǎng)度的情況下，前綴、后綴字符串是確定的。如果前綴字符串等于后綴字符串，將這種情況叫做相同前后綴。在所有相同前后綴字符串中，長(zhǎng)度最長(zhǎng)的叫做最長(zhǎng)相同前后綴。

1. pattern = "a" ， 沒(méi)有前后綴，長(zhǎng)度為0或者1的字符串沒(méi)有前綴或后綴
2. pattern = "abcda" ， 相同前后綴有"a"，最長(zhǎng)相同前后綴為"a"
3. pattern = "aacaa" ， 相同前后綴有"a"、"aa"，最長(zhǎng)相同前后綴為"aa"
4. pattern = "abcabca" ， 相同前后綴有"a"、"abca"，最長(zhǎng)相同前后綴為"abca"

前后綴長(zhǎng)度數(shù)組（next數(shù)組）

對(duì)于一個(gè)給定的字符串pattern（長(zhǎng)度為）,對(duì)于pattern的每個(gè)字串pattern[0:i]，計(jì)算出每個(gè)字串的最長(zhǎng)相同前后綴的長(zhǎng)度，由此構(gòu)成的數(shù)組為前后綴長(zhǎng)度數(shù)組，也就是next數(shù)組。

pattern = "abcaabca"

1. i = 0 ， 子串為"a"， 沒(méi)有前后綴，next[0]=0
2. i = 1 ， 子串為"ab"，沒(méi)有相同前后綴， next[1] = 0
3. i = 2 ， 子串為"abc"， 沒(méi)有相同前后綴，next[2] = 0
4. i = 3 ， 子串為"abca"，最長(zhǎng)相同前后綴為"a"，next[3] = 1
5. i = 4 ， 子串為"abcaa"， 最長(zhǎng)相同前后綴為"a"， next[4] = 1
6. i = 5 ， 子串為"abcaab"， 最長(zhǎng)相同前后綴為"ab"，next[5] = 2
7. i = 6 ， 子串為"abcaabc"，最長(zhǎng)相同前后綴為"abc"，next[6] = 3
8. i = 7 ， 子串為"abcaabca"，最長(zhǎng)相同前后綴為"abca"，next[7] = 4

這里我們通過(guò)設(shè)置不同的前后綴長(zhǎng)度，來(lái)找到每個(gè)字串的最長(zhǎng)相同前綴長(zhǎng)度，形成next數(shù)組。按照這個(gè)設(shè)置不同前后綴長(zhǎng)度，產(chǎn)生前后綴，并確認(rèn)是否相同的方法，計(jì)算next數(shù)組的復(fù)雜度為，實(shí)際上，next數(shù)組能在的時(shí)間復(fù)雜度內(nèi)計(jì)算出來(lái)。

在介紹如何快速計(jì)算next數(shù)組前，我們先看看如何利用next數(shù)組來(lái)快速在text中找到pattern，這個(gè)快速查找的技巧也會(huì)用在快速計(jì)算next數(shù)組中。

假設(shè)text="abcabcabf"，pattern="abcabf"，進(jìn)行字符串匹配，表示text的下標(biāo)，表示pattern的下標(biāo)。剛開(kāi)始，我們很容易將text[0:4]與pattern[0:4]對(duì)應(yīng)上，但是對(duì)比text[5]和pattern[5]時(shí)，由于"c"不等于"f"，所以這次匹配失敗了。

但是我們不用在把設(shè)置為1，設(shè)置為0，進(jìn)行暴力匹配。我們可以保持當(dāng)前的"c"不變，將設(shè)置為2，繼續(xù)比較text[5]和pattern[2]。

這是因?yàn)閜attern[0:4]的最長(zhǎng)相同前后綴為"ab"，所以pattern[0:1]=pattern[3:4]="ab"，而由于text[0:4]與pattern[0:4]時(shí)匹配的，所以有text[0:1]=text[3:4]="ab"，所以就有text[3:4]=pattern[0:1]，然后就是將繼續(xù)向后遍歷對(duì)比，剛好可以完全匹配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