2021-11-25：给定两个字符串s1和s2，返回在s1中有多少个子串等于s2。来自美团。

答案2021-11-25：

改写kmp算法。
next数组多求一位。
比如：str2 = aaaa，
那么，next = -1,0,1,2,3。
最后一个3表示，终止位置之前的字符串最长前缀和最长后缀的匹配长度。
也就是next数组补一位。
时间复杂度：O((N)。
空间复杂度：O(N)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {

    str1 := "aaaab"

    str2 := "aaa"

    ret := sa(str1, str2)

    fmt.Println(ret)

}

func sa(s1, s2 string) int {

    if len(s1) < len(s2) {

        return 0

    }

    str1 := []byte(s1)

    str2 := []byte(s2)

    return count(str1, str2)

}

// 改写kmp为这道题需要的功能

func count(str1 []byte, str2 []byte) int {

    x := 0

    y := 0

    count := 0

    next := getNextArray(str2)

    for x < len(str1) {

        if str1[x] == str2[y] {

            x++

            y++

            if y == len(str2) {

                count++

                y = next[y]

            }

        } else if next[y] == -1 {

            x++

        } else {

            y = next[y]

        }

    }

    return count

}

// next数组多求一位

// 比如：str2 = aaaa

// 那么，next = -1,0,1,2,3

// 最后一个3表示，终止位置之前的字符串最长前缀和最长后缀的匹配长度

// 也就是next数组补一位

func getNextArray(str2 []byte) []int {

    if len(str2) == 1 {

        return []int{-1, 0}

    }

    next := make([]int, len(str2)+1)

    next[0] = -1

    next[1] = 0

    i := 2

    cn := 0

    for i < len(next) {

        if str2[i-1] == str2[cn] {

            cn++

            next[i] = cn

            i++

        } else if cn > 0 {

            cn = next[cn]

        } else {

            next[i] = 0

            i++

        }

    }

    return next

}