NC149 KMP algorithm – find the number of times a pattern string occurs in a text string

Topic link

Find the number of times a pattern string occurs in a text string. The basic implementation of KMP algorithm can be adjusted slightly.

The following code has been submitted for approval.

package main

/** * The class name, method name and parameter name have been specified, do not modify, @param T string String template string @param T string string text string @return int int */
func kmp( S string ,  T string ) int {
    // write code here
    if S == "" {
        return 1
    }
    sl := len(S)
    tl := len(T)
    if sl > tl { // The pattern string is longer than the text string and returns directly
        return 0
    }
    var (
        si int
        ti int
        next = getNextArray(S)
        c int
    )
    for ti < tl {
        if S[si] == T[ti] {
            si++
            ti++
            if si == sl {
                c++
                si = next[si- 1] / / keep looking}}else if si == 0 {
            if tl-ti < sl { // The pattern string is longer than the rest of the text string
                break
            }
            ti++
        } else {
            si = next[si- 1]}}return c
}

func getNextArray(p string) []int {
    var (
        j int
        i = 1
        l = len(p)
        next = make([]int, l)
    )
    for i < l {
        if p[i] == p[j] {
            j++
            next[i] = j
            i++
        } else if j == 0 {
            next[i] = 0
            i++
        } else {
            j = next[j- 1]}}return next
}
Copy the code