相关题目链接: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];
// 匹配成功后的逻辑
}
}
标签:匹配,int,模式,next,算法,详解,kmp,下标
From: https://www.cnblogs.com/lxing-go/p/17388507.html