C/C++教程

Manacher算法学习与应用

本文主要是介绍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算法学习与应用的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!