KMP算法--golang

串匹配--KMP算法

next数组

首先我们先要了解一下什么是字符串的前缀和后缀

前缀

字符串的前缀是指字符串的任意首部。比如：望，望江，望江楼，望江楼上.......

后缀

字符串的任意尾部是字符串的后缀。比如：流，江流，江江流，望江江流......

前缀和后缀的公共子串

字符串前缀和后缀相同的字串。比如：“望江楼上望” 中的字串“望”， “望江楼上望江”中的“望江”

图解求next数组

第一个字符前没有字符串，对应数组的值为-1（默认的）

第二个字符前的字符串，没有公共子串（从这里开始，next数组对应的值是.公共子串的长度）

第三个字符前的字符串，没有公共子串

第四个字符前的字符串，没有公共子串

第五个字符前的字符串，没有公共子串

第六个字符前的字符串，出现了公共子串“望”，长度是1，对应数组的值：1

第七个字符前的字符串，出现了公共子串“望江”，长度是2，对应数组的值：2

第八个字符前的字符串，没有公共子串

代码实现

package main

import "fmt"

func main() {
    var str string = "望江楼上望江江流"

    text := []rune(str)
    next := next(text)

    for _, i2 := range next {
        fmt.Printf("%d，", i2)
    }
}

func next(str []rune) []int {

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

    k := -1 //记录公共子串的长度
    j := 0

    for j < strLength-1 {
        if k == -1 || str[k] == str[j] {
            k++
            j++
            next[j] = k
        } else {
            k = next[k]
        }
    }

    return next

}

运行结果：-1，0，0，0，0，1，2，0，

kmp算法

KMP算法的思想就是：在匹配过程称，若发生不匹配的情况，如果next[j]>=0，则目标串的指针i不变，将模式串的指针j移动到next[j]的位置继续进行匹配；若next[j]=-1，则将i右移1位，并将j置0，继续进行比较。

图解

第一次匹配

第四个字符失配。字串的初始值为对应的第四个字符的next数组中的值 0。

第二次匹配

由于前三个是匹配的，而第四个字符失配，没有公共字串，那么无需再比较前三个字符。

这里的长串索引没有初始化，还是上次失配的值，就是3

短串初始值是0

第三次匹配

第三个字符失配，短串初始值为对应的next数组中的0

第四次匹配

第一个字符失配（就将长串索引+1，字串索引+1，代码中会有一个判断）

第五次匹配

第一个字符失配（就将长串索引+1，字串索引+1，代码中会有一个判断）

第六次匹配

第七个字符失配。出现了公共字串“望江”，下次字串的索引初始值是对应的2。

第七次匹配

长串的索引值还是上次失配的地方的值：14

短串初始值：2

后面的就省略了

........

代码

package main

import "fmt"

func main() {
    var shortStr string = "望江楼上望江江流"
    var longStr string = "望江楼，望江流，望江楼上望江流，江楼千古，江流千古"
    shortText := []rune(shortStr)
    longText := []rune(longStr)

    result := kmp(shortText, longText)

    if result == -1 {
        fmt.Println("没有匹配到")
    }else {
        fmt.Println("匹配到首次出现的索引位置是：", result)
    }

}

func kmp(shortStr, longStr []rune) int{

    shortStrLen := len(shortStr)
    longStrLen := len(longStr)

    if shortStrLen > longStrLen {
        return -1
    }

    var i int = 0 //长串索引
    var j int = 0 //短串索引

    next := next(shortStr)

    for i < longStrLen {
        if j== -1 || longStr[i] == shortStr[j] {
            i++;
            j++;
        }else {
            j = next[j];
        }

        if j == shortStrLen {
            return i - j
        }

    }
    return -1
}

func next(str []rune) []int {

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

    k := -1 //记录公共子串的长度
    j := 0

    for j < strLength-1 {
        if k == -1 || str[k] == str[j] {
            k++
            j++
            next[j] = k
        } else {
            k = next[k]
        }
    }

    return next
}