kmp算法详解

xiaoXingcode-go / 2023-05-10 / 原文

相关题目链接：LeetCode 28. 找出字符串中第一个匹配项的下标

代码如下


func strStr(s string, p string) int {
    //kmp算法，下标一般从1开始，
    //next数组表示的是最长相等前后缀的长度，也就是最少移动几位，使得前后缀相等，
    // s是主串，p是模式串
    n:=len(s)
    m:=len(p)
    s = " " +s 
    p = " "+ p 
    next:=make([]int,m+1)
    //求next数组的过程，其实也是一个匹配的过程，也就是相当于自己和 错一位的自己匹配
    for i,j:=2,0;i<=m;i++{  
        for j>0 && p[i] != p[j+1]{  
            j = next[j]
        }
        if p[i] == p[j+1]{
            j++
        }
        next[i] = j  //记录下当前的匹配值
    }

    //匹配过程  ，主串 下标从1 开始，模式串下标从0开始
    for i,j:=1,0;i <=n;i++{
        for j>0 && s[i] != p[j+1]{  //只要模式串的指针不在起始位置，同时 主串 与 模式串 不匹配，则回退到next[j] 的位置
            j = next[j]
        }
        if s[i] == p[j+1] {  //如果匹配了，那就进行下一个匹配
            j++
        }
        if j== m{  //如果已经匹配到最后了，匹配成功，
            return i-m
        }
    }
    return -1





}

求next数组的代码模板：

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}