什么是最小前缀和后缀？
在计算机科学中，最小前缀和后缀是指一个字符串的前缀（不包括它本身）和后缀（不包括它本身）中，最小共有的字符数量。例如，字符串"abcdab"的前缀为"a", "ab", "abc", "abcd", "abcda"，后缀为"b", "ab", "dab", "cdab", "bcdab"，其中最小共有的字符数量为2，即"ab"。
在字符串匹配中，最小前缀和后缀是一个非常重要的概念。通过计算给定字符串的最小前缀和后缀的数量，可以确定字符串匹配的有效边界。
朴素算法
算法思想
朴素算法也叫暴力算法，是一种简单直接的字符串匹配算法。其基本思想是，将模式串与文本串的每个子串进行比较，找到匹配的子串。
在朴素算法中，计算最小前缀和后缀的数量的方式是，对于每个子串，从头开始往后依次比较每个字符，直到找到最大的共同前缀和后缀。
int minPrefixSuffix(string s) {
int n = s.size();
for (int i = n - 1; i >= 1; i--) {
bool flag = true;
for (int j = 0; j < i; j++) {
if (s[j] != s[n - i + j]) {
flag = false;
break;
}
}
if (flag) {
return i;
}
}
return 0;
}
这个算法的时间复杂度为$O(n^3)$，其中$n$为字符串的长度，显然不够高效。
算法改进
我们可以观察到，计算最小前缀和后缀的数量的过程涉及到了很多次重复比较。例如，在计算子串"s[0:i]"和子串"s[n-i:n]"的最大共同前缀和后缀的时候，我们已经比较了子串"s[0:i-1]"和"s[n-i+1:n]"的最大共同前缀和后缀了。
因此，我们可以通过记录已经算过的最大共同前缀和后缀，来避免重复比较。我们定义数组$pi$，其中$pi[i]$表示子串$s[0:i]$的最大共同前缀和后缀的长度。
假设我们已经计算出了$pi[i-1]$，现在来计算$pi[i]$。我们发现，如果$s[pi[i-1]]$和$s[i]$相等，那么$s[0:i]$的最大共同前缀和后缀就是$s[0:pi[i-1]+1]$的最大共同前缀和后缀再加1。否则，我们需要在已知的$pi[i-1]$和$s[0:i-1]$的最大共同前缀和后缀中找到更小的一个，这样才能使$s[0:i]$和$s[n-i:n]$的最大共同前缀和后缀也更小。
vector<int> prefixFunction(string s) {
int n = s.size();
vector<int> pi(n, 0);
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j > 0 && s[i] != s[j]) {
j = pi[j - 1];
}
if (s[i] == s[j]) {
j++;
}
pi[i] = j;
}
return pi;
}
int minPrefixSuffix(string s) {
int n = s.size();
vector<int> pi = prefixFunction(s);
return pi[n - 1];
}
这个算法的时间复杂度为$O(n)$，其中$n$为字符串的长度。我们可以发现，通过利用已知的信息，避免重复计算，算法的效率得到了极大的提高。
KMP算法
算法思想
KMP算法是由Donald Knuth、Vaughan Pratt和James Morris于1977年联合发表的，它是一个高效的字符串匹配算法，可以在$O(m+n)$的时间复杂度内找到模式串在文本串中的位置，并且可以计算出模式串的最小前缀和后缀的数量。
我们已经知道了如何计算模式串的最小前缀和后缀的数量，现在的问题是如何在匹配字符串的过程中同时计算它。
与朴素算法相同，我们需要先预处理文本串和模式串的最大共同前缀和后缀。我们定义数组$pi$，其中$pi[i]$表示模式串$pat[0:i]$的最大共同前缀和后缀的长度。
考虑在匹配字符串的过程中，如何基于已知的$pi$来计算匹配上的最小前缀和后缀的数量。
假设文本串匹配到了位置$i$，模式串匹配到了位置$j$，那么最小前缀和后缀的数量为$j - pi[j-1]$。
这个结论的依据是，由于文本串和模式串是从左往右进行匹配，匹配上的长度肯定不会超过$j$，而由于$pi[j-1]$表示模式串$pat[0:j-1]$的最大共同前缀和后缀的长度，所以匹配上的长度最大为$j-pi[j-1]-1$。那么最小前缀和后缀的数量就等于$j-j-pi[j-1]+1$，即$j-pi[j-1]$。
通过以上分析，我们可以在KMP算法中同时求解模式串的最小前缀和后缀的数量。
vector<int> prefixFunction(string s) {
int n = s.size();
vector<int> pi(n, 0);
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j > 0 && s[i] != s[j]) {
j = pi[j - 1];
}
if (s[i] == s[j]) {
j++;
}
pi[i] = j;
}
return pi;
}
int KMP(string text, string pattern) {
int n = text.size(), m = pattern.size();
vector<int> pi = prefixFunction(pattern);
int j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && pattern[j] != text[i]) {
j = pi[j - 1];
}
if (pattern[j] == text[i]) {
j++;
}
if (j == m) {
return i - m + 1; // 匹配成功
}
}
return -1; // 匹配失败
}
int minPrefixSuffix(string s) {
int n = s.size();
vector<int> pi = prefixFunction(s);
return pi[n - 1];
}
这个算法的实现的时间复杂度是$O(m+n)$，其中$m$和$n$分别为模式串和文本串的长度。
Manacher算法
算法思想
Manacher算法是一种高效的计算最小前缀和后缀的数量的算法，因为和KMP算法一样，它可以在$O(n)$的时间复杂度内完成。
Manacher算法和前面两个算法不同的是，它利用了回文串的对称性，通过避免重复计算，进一步提高了算法的效率。
在计算最小前缀和后缀的数量的时候，Manacher算法的思路是，对于从某个点出发的回文串，在其边界和中心位置处，必然可以找到一些对称的位置，我们可以利用这些对称性，来避免重复计算。
我们遍历字符串，从第一个字符开始计算，然后依次向两侧扩展，直到回文串不能再扩展为止。我们用$r$表示当前回文串的右边界，$c$表示当前回文串的中心位置。对于当前的位置$i$，我们可以分两种情况考虑。
如果$i$在回文串中，那么我们可以利用关于$c$对称的位置$j = 2c - i$，来避免重复计算。因为$c+(c-i)$是回文串中心位置的对称位置。
如果$i$不在回文串中，那么我们需要逐一比较$i$左边和右边的字符是否相同，来寻找以$i$为中心的最长回文子串。
如此循环，我们就可以找到所有以$i$为中心的回文串。同时，我们需要维护一个以往的回文串中，最右端的位置和中心位置。在遍历过程中，我们可以在$O(1)$时间内得到以$i$为中心的最长回文串的长度。
string preprocess(string s) {
int n = s.size();
string t(2 * n + 1, '#');
for (int i = 0; i < n; i++) {
t[2 * i + 1] = s[i];
}
return t;
}
int minPrefixSuffix(string s) {
string t = preprocess(s);
int n = t.size();
vector<int> p(n, 0);
int c = 0, r = 0;
for (int i = 0; i < n; i++) {
int j = c - (i - c);
if (r > i) {
p[i] = min(r - i, p[j]);
}
while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && t[i - p[i] - 1] == t[i + p[i] + 1]) {
p[i]++;
}
if (i + p[i] > r) {
c = i;
r = i + p[i];
}
}
int ans = 0;
for (int i = 1; i < n; i += 2) {
ans = max(ans, min(p[i], (i + 1) / 2));
}
return ans;
}
这个算法的实现的时间复杂度是$O(n)$，其中$n$为字符串的长度。它是最快的计算最小前缀和后缀的数量的算法之一。
总结
以上就是几种计算最小前缀和后缀的数量的算法。它们分别是朴素算法、KMP算法和Manacher算法。我们发现，这几种算法都可以在$O(n)$的时间复杂度内完成，其中Manacher算法是最快的。
在实际应用中，我们通常使用KMP算法来进行字符串匹配，在需要计算接口哈希值等场景下，使用Manacher算法来计算最小前缀和后缀的数量。
除了这些算法，还有一些其他的算法也可以用于字符串匹配，例如Rabin-Karp算法、Boyer-Moore算法等。
对于求解字符串相关问题，我们需要不断学习和积累。希望这篇文章对您有所帮助！