Manacher算法学习与应用

本文主要是介绍Manacher算法学习与应用，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

提出问题

给出一个字符串，要求字符串的最长回文子串，怎么办？

最暴力的做法（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算法的基础讲解和代码实现，以及一个基础应用就讲到这里了。由于本人能力有限，如有不正确或者有瑕疵的地方，还请指正！！谢谢！

这篇关于Manacher算法学习与应用的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！