Golang leetcode28 找出字符串中第一个匹配项的下标 KMP算法详解

发布时间:2024年01月21日

找出字符串中第一个匹配项的下标 leetcode28 串的模式匹配问题

暴力求解

func strStr(haystack string, needle string) int {
L := len(needle)
Cap := len(haystack)

H := []byte(haystack)
N := []byte(needle)

for i, val := range H {

if val == N[0] {
if i+L <= Cap && haystack[i:i+L] == needle {
return i
}
}
}
return -1
}

使用KMP模式匹配算法

KMP算法简述

当出现字符串不匹配时,可以记录一部分之前已经匹配的文本内容,利用这些信息避免从头再去做匹配。
其主要的用途就是查找字符串,从主字符串中寻找模式字符串
其相比暴力解法,时间复杂度从O(mXn)》O(m+n)

所以如何记录已经匹配的文本内容,是KMP的重点,也是next数组肩负的重任。

什么叫字符串的前缀后缀
对于字符串ababc 来说,它的前缀[a,ab,aba,abab],也就是以字符串第一个字符作为开头,同时不包括最后一个字符的所有子串,
同理它的后缀[c,bc,abc,babc],也就是以字符串最后一个字符作为结尾,同时不包括第一个字符的所有字串。

  1. 思路分析
    当我们进行字符串匹配时,假如第一次匹配失败时如图所示
    在这里插入图片描述

第4个字母不一致,但前三个字母是一致的,那么当我们继续寻找时,没有必要再从第一个字母开始对应
在这里插入图片描述

为什么我们能看出不从第一个字母进行对应呢?
续接我们提到的前后缀的概念,前三个字符为aba,则前缀为a,ab 后缀为 a,ba,二者之中最长的相等的部分为a,一般称这个最长的部分为最长公共前后缀
由此,我们第一个字母a就没有必要再进行比较,直接从第2个字母开始进行比较即可
那么,从这里我们又能够发现,下次从第几个数字开始进行比较,只跟这次重复的子串有关系,
因此我们可以对模式字符串建立一个数组,分别记录当第几个开始不对应时,下次从第几个再开始比较,也就是常说的next
2. next数组(前缀表)
前缀表是用来回退的,它记录了模式串与主串(文本串)不匹配的时候,模式串应该从哪里开始重新匹配。

  1. 使用next数组来进行匹配
    以下我们以前缀表统一减一之后的next数组来做演示。
    有了next数组,就可以根据next数组来 匹配文本串s,和模式串t了。
    注意next数组是新前缀表(旧前缀表统一减一了)。
    这里借用代码随想录中的gif来示意:
    在这里插入图片描述

KMP算法的代码实现

思路可以参考这篇文章

  1. 计算next数组
// 此函数用来初始化next数组
func initNext(needle string) []int {
	//后缀中末尾  abc中c
	i := 1

	//前缀中末尾;同时在这里也有着记录最长公共串长度的作用,二者本质是一样的
	j := 0

	L := len(needle)

	//初始化next数组;next[0]默认为0,因为对于一个字母我们不认为其具有前后缀,后续也不会再对next[0]进行赋值
	next := make([]int, L)

	//求next数组过程中,我们的i不回退,采用类似于动态规划的思想,也是我们这里的循环条件
	for i < L {

		//如果前后缀匹配
		if needle[i] == needle[j] {

			//前缀末尾向后移一位,同时代表长度+1
			j++

			//当前后缀末尾所在位置的最长子串即为j
			//最长子串是有基础的,如果next[2]=2,那么next[3]的可能性为3或者0,这里是为3的情况
			next[i] = j

			//后缀末尾向后移一位
			i++

		} else { //如果前后缀不匹配

			//当j>0,说明仍旧处于回退的过程
			if j > 0 {
				j = next[j-1]
			} else { //如果j=0,并且前后缀依旧不匹配,则长度计数应该重新从0开始

				//这里是为0的情况
				next[i] = j

				//后缀末尾向后移
				i++
			}
		}
	}
	//返回next数组
	return next
}
  1. 利用next数组进行字符串的匹配
// kmp算法,用空间换时间
func strStr(haystack string, needle string) int {
	//获取next数组
	next := initNext(needle)

	//主串长度
	L := len(haystack)

	//目标匹配长度,即needle的长度
	target := len(needle)

	//匹配字符串中指针位置
	j := 0

	//i为主串中指针的位置
	for i := 0; i < L; {

		// 如果匹配上了
		if haystack[i] == needle[j] {
			if j == target-1 {
				return i - target + 1
			}
			j++
			i++
		} else { //如果没匹配上

			//跟计算next数组有异曲同工之妙
			if j > 0 {
				j = next[j-1]
			} else {
				i++
			}

		}
	}

	return -1
}
文章来源:https://blog.csdn.net/kingsill/article/details/135731944
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。