Ltd的算法大抄·KMP算法

这是算法记录的第八天，主要是KMP算法及其题目

对应leetcode题目为28.459

KMP理论

主要是用于字符串匹配。 思想是在字符串匹配的时候，记录下已经匹配到的信息，并利用这些信息来避免重复匹配。

定义

主串：也叫文本串，就是原始的整个字符串

模式串：需要匹配的子串

前缀：以第一个开头，不含最后一个字符的连续子串

后缀：以最后一个结尾，不含第一个字符的连续子串

最长相同前后缀：就是一个字符串的前缀子串和后缀子串最大相同的部分

什么是前缀表

前缀表就是用来回退，当模式串与主串不匹配的时候，前缀表就会告诉我们应该从哪里开始重新匹配。

有点点类似于状态转移表，指向了不匹配时应该跳转（回退）的位置。

前缀表怎么工作

首先前缀表是一个数组，对每一个下标来说，记录下了模式串从开始到当前下标为止的子串中最大公共前后缀的长度。

前缀表计算

所以，前缀表是独立于主串的，计算的话也只需用到模式串。具体过程举例来说，下面是以aabba为模式串的前缀表计算。

前缀表工作关键

上面是一个前缀表的计算，那前缀表关键作用是什么（不是所谓的回退）？

每次匹配的位置是当前后缀子串的下一个，如果匹配失败，当前的后缀部分是已经匹配过了的，而有相同前缀的话就可以直接把相同前缀那部分跳过。

假设前缀是A，后缀是B，中间部分是C（模式串变成了A+C+B，C可能不存在），已与后缀匹配的是主串的D部分。一旦D的下一个不匹配，由于A和B是相同的，那么A就不同再和D比较了，而是C的开头与D的下一个继续比较即可。

前缀表与next数组

next数组是具体代码实现的时候用来做回退操作的，一般是有两种形式：

• 一是next就是前缀表
• 一是next是前缀表统一右移一位

求next数组

详细见具体题目及代码

题目

28.找出字符串第一个匹配的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

• 1 <= haystack.length, needle.length <= 104
• haystack 和 needle 仅由小写英文字符组成

思路

KMP算法非常适用，即找到主串中匹配模式串的地方，并返回第一个字符的下标

代码

func strStr(haystack string, needle string) int {
	m, n := len(haystack), len(needle)
	if n == 0 {
		return 0
	}
	next := make([]int, n)
	//求模式串的next数组（前缀表）
	//i，j分别作为后缀子串的尾和前缀子串的尾
	for i, j := 1, 0; i < n; i++ {
		//一次次比较、退回
		for j > 0 && needle[i] != needle[j] {
			//退回上一个
			j = next[j-1]
		}
		//匹配了就移动j
		if needle[i] == needle[j] {
			j++
		}
		//完成一次计算
		next[i] = j
	}
	//对haystack主串遍历
	for i, j := 0, 0; i < m; i++ {
		for j > 0 && haystack[i] != needle[j] {
			//回退到上一个
			j = next[j-1]
		}
		//匹配了就移动j
		if haystack[i] == needle[j] {
			j++
		}
		if j == n {
			//返回第一个匹配的位置
			return i - n + 1
		}
	}
	return -1
}

459.重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba"
输出: false

示例 3:

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示：

• 1 <= s.length <= 104
• s 由小写英文字母组成

思路

这里就不考虑语言内置的字符串匹配函数了

若一个字符串是由重复的子串组成的，那么结构满足泛abab形式（就是a、b可以代表多个字符），那么满足条件的两个相同串s1、s2相加，一定会存在重复子串一部分是由s1的后缀，一部分是s2前缀组成。所以转换成了在s1+s2的串中找s，同时需要除去第一个和最后一个，避免找到的就是s1或s2，这时就可以考虑KMP。

上面是一个思路，但如果考虑KMP算法，里面有前缀表记录下了最长相同前后缀，其中前缀和后缀已经除去最后一个和第一个。

若是重复子串S，最长相等前缀设为A（后缀也是A），那么S-A就是重复的最小单位，因为前缀和后缀要除去最后一个和第一个，会导致一个重复的最小单位是没法纳入其中。

所以，当一个字符串是重复子串构成，那么重复的最小单位就是字符串本身除去最长相同前后缀剩下的部分。

这样S的长度如能被重复的最小单位整除，说明S就是由重复子串构成的。

代码

//借用了kmp求next数组的过程
func repeatedSubstringPattern(s string) bool {
	n := len(s)
	if n == 0 {
		return false
	}
	next := make([]int, n)
	//获取S的next数组，其实需要的只是最后一个值（整个S的最长相同前后缀的长度）
	for i, j := 1, 0; i < n; i++ {
		for j > 0 && s[i] != s[j] {
			j = next[j-1]
		}
		if s[i] == s[j] {
			j++
		}
		next[i] = j
	}
	//next[n-1]就是长度为n的串最长相同前后缀的长度
	//若s满足要求，那么n-next[n-1]就是最小重复单位的长度，那么就会整除s，若不是就不会了
	if next[n-1] != 0 && n%(n-next[n-1]) == 0 {
		return true
	}
	return false
}

总结

之前学数据结构的时候KMP学得有点糊涂，埋下了恐惧的种子，加上时间一久，所以再遇感觉有点怕。

不过现在仔细的分析、理解，似乎也就那样吧，主要就是利用前后相同的部分省去了再次比较的过程，而两步内容也基本相同，都有步进、回退，只是一个是生成next，一个是利用next对原字符串进行比对。

不过理解是一回事，真正完整地实现代码是另一回事，对于next实现上，有的初始是-1，有的就是0，对于两种情况还不太理解，需要进一步思考（这里-1，那里就要+1，那为什么不就默认0就是了？下标有对齐？）；同时对于代码的具体实现能力也还需要提升吧。

• ← Previous Post
• Next Post →