定义
前缀函数
前缀函数（π数组），也叫即最长真前缀真后缀（lps数组，Longest prefix which is also suffix）。
过程
定义i, j两个指针，i用于匹配后缀，j用于匹配前缀，初始时i = 1, j = 0。
pattern[i] == pattern[j]时，匹配成功，j++，lps[i] = j。
pattern[i] != pattern[j]时，匹配失败，若j != 0（即存在已经匹配的前缀pattern[0...j - 1]），此时有pattern[0...j - 1] == pattern[i - j...i - 1]。
此时pattern[i - j...i - 1]（也就是pattern[0...j - 1]）无法作为pattern[i]和pattern[j]的共同前缀，因此需要在pattern[0...j - 1]中找到一个最长真前缀（这个前缀同时也是pattern[i - j...i - 1]（也就是pattern[0...j - 1]）的最长真后缀）使得pattern[i] == pattern[j]，即需要找到pattern[0...j - 1]的最长真前缀真后缀，所以令j = lsp[j - 1]，若依然pattern[i] != pattern[j]，重复上述操作，直至匹配成功（j++，lps[i] = j）或j == 0（lsp[i] = 0）。
模版
int N, lps[N]; \\ lps[i]默认为0
void LPS(string pattern)
{
for (int i = 1, j = 0; i < pattern.size(); i++)
{
while (j > 0 && pattern[i] != pattern[j]) \\ 匹配失败
j = lps[j - 1]; \\ 从最长真前缀真后缀开始寻找下一个可能的前缀
if (pattern[i] == pattern[j]) \\ 匹配成功
lps[i] = ++j;
}
}示例
对于字符串str = ababac
| i | str[0…i] | lps[i](π[i]) | |
|---|---|---|---|
| 0 | a | 0 | 规定lsp[0] = 0 |
| 1 | ab | 0 | 没有相等的真前缀和真后缀 |
| 2 | aba | 1 | 最长真前缀真后缀为a |
| 3 | abab | 2 | 最长真前缀真后缀为ab |
| 4 | ababa | 3 | 最长真前缀真后缀为aba |
| 5 | ababac | 0 | 没有相等的真前缀和真后缀 |