[toc]

一、KMP算法說明

要判斷s1字符串是否包含s2字符串，如果包含返回s1中包含s2的最左開頭位置，不包含返回-1

暴力方法就是s1的每個位置都做開頭，然后去匹配s2整體，時間復(fù)雜度O(n*m)，其中n為s1長度，m為s2長度

KMP算法可以做到時間復(fù)雜度O(n+m)

二、詳細實現(xiàn)

1. next數(shù)組定義

字符串s的next數(shù)組為int數(shù)組，長度等于s的長度。next[i]表示在s中下標(biāo)i之前子串的<font color="red">前綴和后綴的最大匹配長度</font>(不包含整體)

以字符串"aabaabs"為例

// i=0,規(guī)定next[0]為-1
// i=1,由于s[1]之前只有a，除去整體，前綴和后綴只能是空，所以規(guī)定next[1]=0
// i=2, "aa",前綴"a",后綴"a"，最大匹配長度1，next[2]=1
// i=3, "aab",沒有可以匹配的前綴和后綴，next[3]=0
// i=4, "aaba", 前綴"a", 后綴"a", next[4]=1
// i=5, "aabaa", 前綴"aa", 后綴"aa", next[5]=2
// i=6, "aabaab", 前綴"aab", 后綴"aab", next[6]=3
// 擴充的next是可以多計算一位的
// i=7, "aabaabs",沒有可以匹配的前綴和后綴，next[7]=0

2. 使用next加速匹配

func kmp(s1, s2 string) int {
    if len(s1) < len(s2) {
        return -1
    }
    next := nextArr(s2)
    x, y := 0, 0
    for x < len(s1) && y < len(s2) {
        if s1[x] == s2[y] {
            x++
            y++
        } else if y > 0 {
            y = next[y]
        } else {
            x++
        }
    }
    if y == len(s2) {
        return x - y
    } else {
        return -1
    }
}

3. next數(shù)組如何快速生成

func nextArr(s string) []int {
    if len(s) <= 1 {
        return []int{-1}
    }
    next := make([]int, len(s))
    next[0], next[1] = -1, 0
    cp := 0
    for i := 2; i < len(s); {
        if s[i-1] == s[cp] {
            cp++
            next[i] = cp
            i++
        } else if cp > 0 {
            cp = next[cp]
        } else {
            next[i] = 0
            i++
        }
    }
    return next
}

4. 時間復(fù)雜度O(m+n)的證明

a) next生成的時間復(fù)雜度

// for循環(huán)中我們關(guān)注i和i-cp
// i的范圍是2~m
// i-cp的范圍是0~m
// 分支1:i變大, i-cp不變
// 分支2:i-cp變大
// 分支3:i變大，i-cp變大
// 因此時間復(fù)雜度O(m)

b) 匹配過程時間復(fù)雜度

// for循環(huán)中關(guān)注x和x-y
// ...
// 同理時間復(fù)雜度O(n)

三、例題

1. leetcode#572

[圖片上傳失敗...(image-5964c0-1711559891493)]

// 思路：將兩棵樹都序列化為sRoot和sSubRoot，然后判斷sSubRoot是否為sRoot的子串

func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
    const nullVal = 1e4 + 1
    var s1, s2 []int
    s1 = encode(root, make([]int, 0), nullVal)
    s2 = encode(subRoot, make([]int, 0), nullVal)
    return kmp2(s1, s2) >= 0
}
func encode(root *TreeNode, list []int, nullVal int) []int {
    if root == nil {
        list = append(list, nullVal)
        return list
    }
    list = append(list, root.Val)
    list = encode(root.Left, list, nullVal)
    list = encode(root.Right, list, nullVal)
    return list
}
func kmp2(s1, s2 []int) int {
    if len(s1) < len(s2) {
        return -1
    }
    next := nextArrInt(s2)
    x, y := 0, 0
    for x < len(s1) && y < len(s2) {
        if s1[x] == s2[y] {
            x++
            y++
        } else if y > 0 {
            y = next[y]
        } else {
            x++
        }
    }
    if y == len(s2) {
        return x - y
    } else {
        return -1
    }
}
func nextArrInt(s []int) []int {
    if len(s) <= 1 {
        return []int{-1}
    }
    next := make([]int, len(s))
    next[0], next[1] = -1, 0
    cp := 0
    for i := 2; i < len(s); {
        if s[i-1] == s[cp] {
            cp++
            next[i] = cp
            i++
        } else if cp > 0 {
            cp = next[cp]
        } else {
            next[i] = 0
            i++
        }
    }
    return next
}

2. leetcode#1367

[圖片上傳失敗...(image-a6235b-1711559891493)]

func isSubPath(head *ListNode, root *TreeNode) bool {
    if head == nil {
        return true
    }
    if root == nil {
        return false
    }
    list := make([]int, 0)
    for head != nil {
        list = append(list, head.Val)
        head = head.Next
    }
    next := nextArrInt(list)
    return find(root, list, next, 0)
}

func find(cur *TreeNode, list []int, next []int, index int) bool {
    if index == len(list) {
        return true
    }
    if cur == nil {
        return false
    }
    for index >= 0 && cur.Val != list[index] {
        index = next[index]
    }
    // index=-1 => index=0
    // 匹配 => index+1
    index++
    return find(cur.Left, list, next, index) || find(cur.Right, list, next, index)
}