网站链接: ngui
当前位置: 首页 > 学习教程  > 编程语言

Manacher算法图解

2020/11/22 5:48:13 人评论 文章标签: 图解h

看了好久的Manacher算法,觉得还是要自己画一遍,自己把代码写一遍才能理解 下面分享一下,如果有错,希望指正 简陋版本的,但是他基本只是做到了求取最长回文字符串,严格来说它并不是Manacher’s Algorithm-…

看了好久的Manacher算法,觉得还是要自己画一遍,自己把代码写一遍才能理解

下面分享一下,如果有错,希望指正

简陋版本的,但是他基本只是做到了求取最长回文字符串,严格来说它并不是Manacher’s Algorithm-马拉车算法

#include<stdio.h>   、

char qdu[100050];
int manachar()
{
	int i;
	int res = 0;
	for (i = 1; qdu[i]; i++)
	{
		int l = i;
		int r = i;
		while (qdu[i] == qdu[r + 1])
			r++;
		i = r;
		while (qdu[l - 1] == qdu[r + 1]) 
		{
			r++;
			l--;
		}
		if (res < r - l + 1)
			res = r - l + 1;
	}
	return res;
}
int main()
{
	int loop;
	qdu[0] = '$';
	gets(qdu + 1);
	printf("%d\n", manachar());

	return 0;
}

Manacher’s Algorithm-马拉车算法 时间复杂度O(n)

互联网侦察微信公众号讲解,虽然文章很长,但是他讲解的十分清楚

这篇博文简单的介绍了思路

下面是核心代码,我们先看图

//Manacher算法计算过程
int MANACHER(char *st, int len)
{
	int mx = 0, ans = 0, po = 0;//mx即为当前计算回文串最右边字符的最大值
	for (int i = 1; i <= len; i++)
	{
		if (mx > i)
			Len[i] = min(mx - i, Len[2 * po - i]);//在Len[j]和mx-i中取个小
		else
			Len[i] = 1;//如果i>=mx,要从头开始匹配
		while (st[i - Len[i]] == st[i + Len[i]])
			Len[i]++;
		if (Len[i] + i > mx)//若新计算的回文串右端点位置大于mx,要更新po和mx的值
		{
			mx = Len[i] + i;
			po = i;
		}
		ans = max(ans, Len[i]);
	}
	return ans - 1;//返回Len[i]中的最大值-1即为原串的最长回文子串额长度 
}

首先对字符串进行预处理,处理原因是防止偶数问题(可看前面的博文)
处理后的结果进行Manacher算法。
第一个@是0,其余默认从1开始计数
首先看3 的左右都是#号所以1+1 = 2;
到了1,它可以数到6,碰到了@就不相等了,而他的回文字符串长度也是6
等到了1右边的#号,我们就可以根据对称特点,求出他和1左边的#号是同一个值(前提是这个没有超过有边界,黄色横线所示)
到这里基本就结束了
在这里插入图片描述

在这里插入图片描述

这里给出完整代码,可以自己跑一编,看看效果

#define maxn 1000010
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

char str[maxn] = {"3212343219"};//原字符串
char tmp[maxn << 1];//转换后的字符串
int Len[maxn << 1];

//转换原始串
int INIT(char *st)
{
	int i, len = strlen(st);
	tmp[0] = '@';//字符串开头增加一个特殊字符,防止越界
	for (i = 1; i <= 2 * len; i += 2)
	{
		tmp[i] = '#';
		tmp[i + 1] = st[i / 2];
	}
	tmp[2 * len + 1] = '#';
	tmp[2 * len + 2] = '$';//字符串结尾加一个字符,防止越界
	tmp[2 * len + 3] = 0;
	return 2 * len + 1;//返回转换字符串的长度
}
//Manacher算法计算过程
int MANACHER(char *st, int len)
{
	int mx = 0, ans = 0, po = 0;//mx即为当前计算回文串最右边字符的最大值
	for (int i = 1; i <= len; i++)
	{
		if (mx > i)
			Len[i] = min(mx - i, Len[2 * po - i]);//在Len[j]和mx-i中取个小
		else
			Len[i] = 1;//如果i>=mx,要从头开始匹配
		while (st[i - Len[i]] == st[i + Len[i]])
			Len[i]++;
		if (Len[i] + i > mx)//若新计算的回文串右端点位置大于mx,要更新po和mx的值
		{
			mx = Len[i] + i;
			po = i;
		}
		ans = max(ans, Len[i]);
	}
	return ans - 1;//返回Len[i]中的最大值-1即为原串的最长回文子串额长度 
}


int main()
{
	int len = INIT(str);
	MANACHER(tmp, len);
}


本文链接: http://xiahunao.cn/news/show-814665.html

附件下载

上一篇:H.264图解

下一篇:YOLO图解

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?