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 //前缀表第一位为0
j := 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 = 0
for 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] = 0
j := 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]) == 0
if prefix[n-1] != 0 && n%(n-prefix[n-1]) == 0 {
return true
}
return false
}