【LeetCode】前缀表相关算法

1、介绍

前缀表是一种在字符串匹配算法（特别是KMP算法）中使用的数据结构，用于高效地搜索模式字符串在文本中的出现位置。它通过预处理模式字符串来存储关键信息，从而避免在匹配失败时进行不必要的回溯。

2、核心概念

【1】前缀和后缀

前缀：字符串开头的一个或多个连续字符（不包含整个字符串）
后缀：字符串结尾的一个或多个连续字符（不包含整个字符串）

例如，对于字符串"abcab"

前缀：“a”、“ab”、“abc”、“abca”
后缀：“b”、“ab”、“cab”、“bcab”

【2】最长公共前后缀（LPS）

指字符串中既是前缀又是后缀的最长子串
例如"abcab"的LPS是"ab"（长度为2）

3、相关算法题

【1】找出字符串中第一个匹配项的下标

LeetCode第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 仅由小写英文字符组成

代码示例：

func strStr(haystack string, needle string) int {n := len(needle)if n == 0 {return -1}//计算前缀表和next := make([]int, n)next[0] = 0 //前缀表第一位为0j := 0      //前缀末尾位置for i := 1; i < n; i++ {//如果不相等就回退再进行比较for j > 0 && needle[i] != needle[j] {j = next[j-1] //此位置为上一个前缀匹配的位置+1}//如果相等就判断下一个位置是否相等if needle[i] == needle[j] {j++}next[i] = j}//根据找出指定字符串位置j = 0for i := 0; i < len(haystack); i++ {for j > 0 && haystack[i] != needle[j] {j = next[j-1]}if haystack[i] == needle[j] {j++}if j == n {return i - n + 1}}return -1
}

【2】重复的子字符串

LeetCode第459题，题目如下：

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

示例 1:

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

示例 2:

输入: s = “aba”
输出: false

示例 3:

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

提示：

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

代码示例：

func repeatedSubstringPattern(s string) bool {n := len(s)if n <= 1 {return false}//构建前缀表prefix := make([]int, n)prefix[0] = 0j := 0 //j表示当前最长相等前后缀长度for i := 1; i < n; i++ {for j > 0 && s[i] != s[j] {j = prefix[j-1] //不匹配时回退}//匹配时前进if s[i] == s[j] {j++}prefix[i] = j}//判断是否由重复子字符串构成//条件1：prefix[n-1] != 0//条件2：n % (n - prefix[n-1]) == 0if prefix[n-1] != 0 && n%(n-prefix[n-1]) == 0 {return true}return false
}