0

go kmp算法

 2 years ago
source link: https://studygolang.com/articles/35372
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

go kmp算法

letterbeezps · 大约5小时之前 · 52 次点击 · 预计阅读时间 1 分钟 · 大约8小时之前 开始浏览    

go KMP

kmp 想必很多人已经知道了，先求next数组，再去匹配

package main
import "fmt"
func main () {

    p := "abcabe"
    s := "abcabfabcabef"

    next := make([]int, len(p))
    next[0] = -1

    // fmt.Println(next)

    j := -1
    for i := 1; i < len(p); i++ {
        for j != -1 && p[i] != p[j+1] {
            j = next[j]
        }

        if p[i] == p[j+1] {
            j ++
        }

        next[i] = j
    }

    fmt.Println("p的next数组：")
    fmt.Println(next)

    j = -1
    for i := 0; i < len(s); i++ {
        for j != -1 && s[i] != p[j+1] {
            j = next[j]
        }

        if s[i] == p[j+1] {
            j ++
        }

        if j == len(p)-1 {
            fmt.Printf("find %s in %s, index is %d", p, s, i-j)
            j = next[j]
        }
    }
}

p的next数组：

[-1 -1 -1 0 1 -1]

find abcabe in abcabfabcabef, index is 6

有疑问加站长微信联系（非本文作者））

280

入群交流（和以上内容无关）：加入Go大咖交流群，或添加微信：liuxiaoyan-s 备注：入群；或加QQ群：701969077


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK