提出问题
给出一个字符串，要求字符串的最长回文子串，怎么办？
最暴力的做法（O(n^3)）
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <cstdlib>
bool isPalindrome(const char* str, int n) {
int j = 0, upper = (n + 1) / 2;
while (j < upper) {
if (str[j] != str[n - j - 1])
return false;
j++;
}
return true;
}
char* getLongestPalind(const char* str) {
int len = (int)strlen(str), ans = 0;
int retp = 0, retq = 0, k = 0;
char* ret = (char*)malloc(sizeof(char) * len);
for (int i = 0; i < len; ++i) {
for (int j = i; j < len; ++j) {
if (isPalindrome(str + i, j - i + 1)) {
if (ans < j - i + 1) {
ans = j - i + 1;
retp = i, retq = j;
}
}
}
}
for (int s = retp; s <= retq; ++s)
ret[k++] = *(str + s);
ret[k] = '\0';
return ret;
}
int main() {
char s[100] = { '\0' };
scanf("%s", s);
printf("%s\n", getLongestPalind(s));
return 0;
}
简单测试一个数据：
再去leetcode上找一个题来测试一下：
在这个问题里就会超时~~
改进的做法（O(n^2)）
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <cstdlib>
char* getLongestPalind(char* str) {
int len = (int)strlen(str), ans = 0, l = 0, r = 0, t = 0;
char* ret = (char*)malloc(sizeof(char) * len + 1);
if (0 == len || 1 == len)
return str;
for (int i = 0; i < len; ++i) {
int j = 0;
while (i - j >= 0 && i + j < len && str[i - j] == str[i + j])
j++;
if (ans < j) {
ans = j;
l = i - j + 1, r = i + j - 1;
}
}
for (int k = l; k <= r; ++k)
ret[t++] = str[k];
ret[t] = '\0';
return ret;
}
int main() {
char s[100] = { '\0' };
scanf("%s", s);
printf("%s\n", getLongestPalind(s));
return 0;
}
这下再去交一下，看看结果哈：
这样就AC了哈~~
这种算法很简单，复杂度是平方级别~
思想就是选定一个中心，然后向两边扩展，求得最长的回文子串~
最好的做法（O(n)）
详解Manacher算法
第一步：扩展原串(padding)
首先，大家伙看完上面那一份代码之后，就会晓得：在处理回文子串的时候，奇数串和偶数串处理起来是不一样的，因为上面那个做法是枚举子串的中心字符，然后两边扩展。但是偶数串是没有中心字符的，它的中心是长度除以二后，的左右两个字符，那样处理是不方便的，所以我们先统一两者，给字符串填充相同，且不会出现在原串中的字符 ‘#’ ，但是上面那份代码在扩展的时候，还是要注意边界，给了些判断条件，防止越界~所以我们干脆再给头尾加上与原串字符、’#’ 都不相同的字符，比如 ‘@’ 、 ‘$’ 等等！
实现第一步的代码：（注意看小注释哦~）
void padding(char* s){
int len = strlen(s), i;
pad[0] = '$';
// pad数组是事先声明好了的~最好是静态初始化哦
pad[1] = '#';
for(i = 0;i < len;++i){
pad[2 * i + 2] = s[i];
pad[2 * i + 3] = '#';
}
pad[2 * len + 2] = '@';
k = 2 * len + 2;
pad[k + 1] = '\0';
// 别忘了字符串要以 '\0' 结尾哦~
}
第二步：分析manacher算法原理
初步理解原理
在manacher算法中，我们需要维护一个数组 p[] ，设定 p[i] 的含义是：以 i 为中心的最长回文半径的长度~设定右边界是rx，初始情况rx = 0，由于之前字符串进行了填充，于是长度由 length = 2 * length + 1（刨去了首位防越界的限定符！），所以这个 p[i] - 1 就会是 length * 2，那么也就是原串回文半径的两倍，这个两倍要注意重复计算了回文中心的字符，于是这个值减1就是最长回文串的长度了~
细究实现细节
大家看到了，能够维护出 p[] 就能得到每个回文子串的长度！！！那么，如何维护它就是技术的重点！
上面这个图是举的一个求 p[] 的示例，我们先来分析一下这个 p[] 如何求得！
对于任意一个位置 i ，假设 j 是 i 关于 id 的对称点，也就是说j = 2 * id - 1，如果 i <= mx，那么对应的 j 也就会在 mx 的对称点的右侧。现在来分类讨论：
第一：如果 j 为中心的最长回文子串左边界在 mx 的对称点的右边
此时，设 L = 以 j 为中心的最长回文子串的左边界 - 1，R = 以 j 为中心的最长回文子串的右边界 + 1
肯定有Str[L] != Str[R] ，否则最长回文子串的左边界就会是 L 了！因为此时必有： p[i] >= p[j] ，如果p[i] 会比 p[j] 大，那么以 i 为中心的最长回文子串的右边界会和它的左边界相同。又因为以 j 为中心的回文子串的左边界 + 1 会和 p[j] 的右边界相同，所以如果 p[i] > p[j]，就会让 L != 以 j 为中心的最长回文子串的左边界 - 1，这就矛盾了！！！
所以此时：p[i] = p[j]
第二：如果 j 为中心的最长回文子串左边界在 mx 的对称点或其左边
首先，如果 j 为中心的最长回文子串左边界超过了 mx 的对称点，举个例子：
e [ a b c b a e f (g) f e a b c b a] y
这里，我们的回文串是以 ‘g’ 为中心的，假设 Str[j] = Str[i] = 'c' ，则此回文子串左侧的 ‘e’ 就有可加入 j 为中心的最长回文子串。但是呢？以 i 为中心的最长回文子串就不可以加入右侧的 ‘y’ ！所以此时，p[i] = mx - i;！
但是如果 j 为中心的最长回文子串左边界恰恰在 mx 的对称点呢？比如：
y [ a b c b a e f (g) f e a b c b a] e
像这种情况呢？？？那么初始情况就只能是：p[i] = p[j]; ！大家可以发现，这两种情况啊在不确定的时候，就是取两者的最小值的！！！于是得到结论：
if(i <= mx)
p[i] = min(p[2 * id - i], mx - i);
这id啊，就是上一步得到的最长回文子串的中心~
第三：如果这个 i > mx 呢？
这个就很简单啦~只需要给 p[i] = 1 初始化就好！因为在初始情况下，我们认为一个字符本身就是回文串~
第四：还是讨论之前的一个问题
我们知道，在第二点里，以 i 为中心的最长回文子串右边界是有可能扩展的，所以需要加个循环判断一下，考虑可能会增加 p[i] 的值。其实这个每种情况都需要考虑，所以要加上：
while (pad[i - p[i]] == pad[i + p[i]])
p[i]++;
第三步：实现Manacher算法的代码：
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
char pad[2005], str[1005];
int k, p[2005];
int min(int a, int b) {
return a < b ? a : b;
}
void padding(char* s) {
int len = strlen(s), i;
pad[0] = '$';
pad[1] = '#';
for (i = 0; i < len; ++i) {
pad[2 * i + 2] = s[i];
pad[2 * i + 3] = '#';
}
pad[2 * len + 2] = '@';
k = 2 * len + 2;
pad[k + 1] = '\0';
}
char* manacher(char* s) {
if (strlen(s) == 0 || strlen(s) == 1)
return s;
int i, rx = 0, id, ans = 0, pos = 0, len = 0, n = 0;
padding(s);
for (i = 1; i < k; ++i) {
if (rx >= i)
p[i] = min(rx - i, p[2 * id - i]);
else
p[i] = 1;
while (pad[i - p[i]] == pad[i + p[i]])
p[i]++;
if (i + p[i] > rx) {
rx = i + p[i];
id = i;
}
if (ans < p[i]) {
ans = p[i];
pos = i, len = p[i] - 1;
}
}
for (int t = pos - len; t < pos + len + 1; ++t)
if ('#' != pad[t])
str[n++] = pad[t];
str[n] = '\0';
return str;
}
int main() {
char t[100] = { '\0' };
scanf("%s", t);
printf("%s\n", manacher(t));
return 0;
}
提交到leetcode上，看看这次的效果如何：
这下效果很明显啊，从40ms到4ms，这是因为复杂度也下降了一个数量级啊！哈哈，再练一道模板题~
练习一道模板题：
洛谷 P3805 【模板】manacher算法
AC代码如下：
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
const int maxn = 2.2e7 + 5;
char pad[maxn], str[maxn / 2];
int k, p[maxn];
int min(int a, int b) {
return a < b ? a : b;
}
void padding(char* s) {
int len = strlen(s), i;
pad[0] = '$';
pad[1] = '#';
for (i = 0; i < len; ++i) {
pad[2 * i + 2] = s[i];
pad[2 * i + 3] = '#';
}
pad[2 * len + 2] = '@';
k = 2 * len + 2;
pad[k + 1] = '\0';
}
int manacher(char* s) {
if (!s)
return 0;
if (strlen(s) == 1)
return 1;
int i, rx = 0, id, ans = 0, pos = 0, len = 0, n = 0;
padding(s);
for (i = 1; i < k; ++i) {
if (rx >= i)
p[i] = min(rx - i, p[2 * id - i]);
else
p[i] = 1;
while (pad[i - p[i]] == pad[i + p[i]])
p[i]++;
if (i + p[i] > rx) {
rx = i + p[i];
id = i;
}
if (ans < p[i])
ans = p[i];
}
return --ans;
}
int main() {
scanf("%s", str);
printf("%d\n", manacher(str));
return 0;
}
Manacher算法的扩展应用
Leetcode 647 回文子串
题目分析：
这个题要求所有回文子串的个数，这个其实本质还是Manacher算法，因为每次维护起来的 p[i] 都是以当前第 i 个位置为中心的最长回文串的长度 + 1，因为我们知道，这个最长回文串左右各减少一个，它仍然是回文串！！于是我们只需要把 (p[i] - 1) / 2 就可以得到所有长度大于1 的回文串的个数，但是要知道一个字符也是一个回文串~所以必须向上取整，也就是：p[i] / 2 ！！
解题代码如下：
char pad[2005];
int k, p[2005];
int min(int a, int b){
return a < b ? a : b;
}
void padding(char* s){
int len = strlen(s), i;
pad[0] = '$';
pad[1] = '#';
for(i = 0;i < len;++i){
pad[2 * i + 2] = s[i];
pad[2 * i + 3] = '#';
}
pad[2 * len + 2] = '@';
k = 2 * len + 2;
pad[k + 1] = '\0';
}
int countSubstrings(char* s){
int i, rx = 0, id, ans = 0;
padding(s);
for(i = 1;i < k;++i){
if(rx > i)
p[i] = min(rx - i, p[2 * id - i]);
else
p[i] = 1;
while(pad[i - p[i]] == pad[i + p[i]])
p[i]++;
if(i + p[i] > rx){
rx = i + p[i];
id = i;
}
ans += p[i] / 2;
}
return ans;
}
解题结果截屏如下：
写在后面
关于Manacher算法的基础讲解和代码实现，以及一个基础应用就讲到这里了。由于本人能力有限，如有不正确或者有瑕疵的地方，还请指正！！谢谢！