Search code examples
stringgoknuth-morris-pratt

the resulting "count" of "pattern" string in not getting print. here is the code


I have tried to implement knuth morris pratt algorithm. the resulting appearance of pattern in the text is not getting printed. the count variable holds the value for how many times a pattern has appeared in the string. Please help resolve the issue

package main

    import "fmt"

    func kmppre(pattern string, shiftarr []int) {
        m := len(pattern)
        i := 0
        j := -1
        for i < m {
            for j >= 0 && pattern[i] != pattern[j] {
                j = shiftarr[j]

            }
            i++
            j++
            shiftarr[i] = j
        }
    }

    func kmp(text string, pattern string) int {
        n := len(text)
        m := len(pattern)
        count := 0
        i, j := 0, 0
        shiftarr := make([]int, m+1)
        kmppre(pattern, shiftarr)
        for i < n {
            for j >= 0 && text[i] != pattern[j] {
                j = shiftarr[j]
            }
            i++
            j++
            if j == m {
                count++
                j = shiftarr[j]
            }

        }
        return count
    }

    func main() {

        fmt.Print("enter the text \n")
        var text string
        fmt.Scan(&text)
        fmt.Print("enter the pattern string\n")
        var pattern string
        fmt.Scan(&pattern)
        a := kmp(text, pattern)
        fmt.Println(a)
    }

Solution

  • for j >= 0 && pattern[i] != pattern[j] {

    should be

    for j > 0 && pattern[i] != pattern[j] {