3407. Substring Matching Pattern

You are given a string s and a pattern string p, where p contains exactly one '*' character.

The '*' in p can be replaced with any sequence of zero or more characters.

Return true if p can be made a substring of s, and false otherwise.

A substring is a contiguous non-empty sequence of characters within a string.

go

func pi(s string) []int {
    PI := make([]int, len(s))
    for i, j := 1, 0; i < len(s); i++ {
        for j > 0 && s[i] != s[j] {
            j = PI[j-1]
        }
        if s[i] == s[j] {
            j++
            PI[i] = j
        }
    }
    return PI
}

func kmp(s, p string) []int {
    if p == "" {
        return []int{}
    }
    PI := pi(p)
    res := []int{}
    for i, j := 0, 0; i < len(s); i++ {
        for j > 0 && s[i] != p[j] {
            j = PI[j-1]
        }
        if s[i] == p[j] {
            j++
            if j == len(p) {
                res = append(res, i-j+1)
                j = PI[j-1]
            }
        }
    }
    return res
}

func hasMatch(s, p string) bool {
    pp := ""
    for len(p) > 0 && p[len(p)-1] != '*' {
        pp = string(p[len(p)-1]) + pp
        p = p[:len(p)-1]
    }
    if len(p) > 0 {
        p = p[:len(p)-1]
    }

    if p == "" && pp == "" {
        return true
    }

    kmp1 := kmp(s, p)
    kmp2 := kmp(s, pp)

    if len(p) == 0 {
        return len(kmp2) > 0
    }
    if len(pp) == 0 {
        return len(kmp1) > 0
    }
    if len(kmp1) == 0 || len(kmp2) == 0 {
        return false
    }

    return kmp1[0]+len(p) <= kmp2[len(kmp2)-1]
}