前缀函数是计算机科学和字符串算法中使用的一种字符串匹配技术。它能够高效地计算出一个数组，该数组表示给定字符串的每个前缀的最长真前缀的长度，该前缀同时也是该子串的后缀。Knuth-Morris-Pratt (KMP) 算法利用前缀函数在线性时间内执行模式匹配，这使得它成为一种在文本中搜索模式出现位置的高效算法。
目录
- 什么是 KMP 算法？
- KMP 算法中的前缀函数是什么？
- 前缀函数和 KMP 算法在算法竞赛中的用例
- 算法竞赛中 KMP 算法的练习题
什么是 KMP 算法？
> Knuth–Morris–Pratt (KMP) 算法是一种线性时间字符串搜索算法，它能高效地在文本中查找模式的出现位置。
KMP 算法中的前缀函数是什么？
前缀函数是 Knuth–Morris–Pratt 算法不可或缺的一部分。
> 字符串 s 的 前缀函数 是一个数组 \pi，其中 \pi[i] 是子串 s[0…i] 的同时也是该子串后缀的最长真前缀的长度。字符串的真前缀是指不等于字符串本身的前缀。显然 \pi[0]=0，因为长度为 1 的字符串没有真前缀。
示例：
> 示例 1： s="xyzxyzxINLINECODEf2a6fbd4s 的前缀函数将是INLINECODE27a70446=[INLINECODE84e5f09es 的前缀函数将是INLINECODEeadf62f3=[0,1,0,1,2,2,3]
### 查找前缀函数（O(N3) 方法）：
> 其思路如下：对于从 0 到 N-1 的所有 i，尝试所有可能的前缀/后缀长度，每次比较的时间复杂度为 O(N)。
下面是上述方法的实现：
C++
CODEBLOCK_4644a182
Java
import java.util.ArrayList;
import java.util.List;
public class PrefixFunction {
// 使用 O(N^3) 方法计算前缀函数的函数
public static List prefixFunction(String s) {
int n = s.length();
List pi = new ArrayList(n);
// 遍历字符串中的每个位置
for (int i = 0; i < n; i++) {
pi.add(0); // 初始化当前位置的值
// 尝试所有可能的前缀/后缀长度
for (int j = 0; j < i; j++) {
// 检查子串是否相等
if (s.substring(0, j + 1).equals(s.substring(i - j, i + 1))) {
pi.set(i, j + 1); // 如果相等，更新当前位置的值
}
}
}
// 返回计算出的前缀函数
return pi;
}
// 驱动代码
public static void main(String[] args) {
String s = "abcabcabc";
List result = prefixFunction(s);
// 打印前缀函数的值
for (int val : result) {
System.out.print(val + " ");
}
System.out.println();
}
}
// 此代码由 akshitaguprzj3 贡献
Python
“
使用 O(N^3) 方法计算前缀函数的函数
def prefix_function(s):
n = len(s)
pi = [0] * n
# 遍历字符串中的每个位置
for i in range(n):
pi[i] = 0 # 初始化当前位置的值
# 尝试所有可能的前缀/后缀长度
for j in range(i):
# 检查子串是否相等
if s[:j + 1] == s[i – j:i + 1]:
pi[i] = j + 1 # 如果相等，更新当前位置的值
# 返回计算出的前缀函数
return pi
驱动代码
if name == "main":
s = "abcabcabc"
res