KMP 算法

参考资料
B站, 印度小哥写的 汪汪都能看懂的KMP算法
印度小哥的代码的github地址

建议多看几遍

本来写了点, 但是觉得写得不好, 又没图, 所以还是删了。

下面是go 语言实现的代码

package main

import (
    "fmt"
)

func main() {
    mainString :="abcxabcdabxabcdabcdabcy"
    // subString := "abcdab";
    // subString :="abcdabc"
    subString :="abcdabcy"
    next := computeNextArray(subString);
    fmt.Println("next----", next)
    idx := KMP(mainString, subString);
    fmt.Println("子串在主串中第一次出现的位置", idx)
}


/**
KMP 
**/
func  KMP(mainString string, subString string) int{
    mainIdx :=0;
    subIdx :=0;
    mainLen :=len(mainString)
    subLen := len(subString)
    next := computeNextArray(subString);
    for  {
        if mainIdx>=mainLen  || subIdx >= subLen{
            //当子串匹配完, 说明主串中包含子串, 需要结束
            //当主串匹配完, 不管子串有没有结束, 都应该不再匹配
            break;
        }

        if mainString[mainIdx] == subString[subIdx]{
            //字符匹配的时候, 主串和子串都往后走
            mainIdx ++;
            subIdx ++;
        }else{
            //不相等的时候, 子串切换到next数组中对应的前一个元素对应的, 需要位移的下标, 进行重新匹配
            if subIdx != 0{
                subIdx = next[subIdx-1]
            }else{
                //当主串元素与子串元素不一样, 且子串回退到了首字符时, 检查主串的下一个字符
                mainIdx++
            }

        }
    }

    //判断结果
    if subIdx>=subLen{
        //说明子串匹配完了, 子串在主串中存在
        return mainIdx - subLen
    }
    //其他情况下, 说明子串没走完, 返回 -1
    return -1

}



//computeNextArray 用于计算子串的 next 数组
func computeNextArray(subString string) []int {
    next := make([]int, len(subString))
    index :=0; 
    i := 1;
    for i < len(subString){
        if subString[i] == subString[index]{
            next[i] = index + 1
            i ++ ;
            index ++;
        }else{
            //不相等的时候
            if index != 0{
                //当index != 0 的时候, 把 next 中, index 前一个元素对应的 next中的值, 赋给 index  
                index = next[index -1]
            }else{
                //当index = 0 的时候,  subString[i] 和 subString[0] , 也就是subString 首字母不相同, 则i向后走
                i++
            }
        }
    }
    return next
}