manacher算法及其应用

最近学习了牛客网的算法初级班，学到了一些经典算法

这里整理一下manacher算法，自己参考老师给的代码，转成C++代码

#ifndef MANACHER_H
#define MANACHER_H
//Manacher算法 :找出字符串str中最长的回文子串
#define MIN(a,b) a<b?a:b
#define MAX(a,b) a>b?a:b
#include<iostream>
#include<vector>
#include<string>
using namespace std;
//字符串改造
//"123abx"
//"#1#2#3#a#b#x#"
string manacherString(string s)
{
	string result = "#";
	for (int i = 0; i != s.length(); ++i)
		result =result +s[i] + "#";
	return result;
}

int manacher(string str)
{
	if (str.length() < 1)//字符串为空
		return 0;
	string s = manacherString(str);//生成扩展字符串
	int R = -1;//最右回文边界的下标，不包括在回文里
	int C = -1;//最右回文半径的中心，随R变化。
	int max = INT_MIN;//用来记录最大回文半径
	vector<int>r(s.length(), 0);//记录每个位置的最大回文半径的数组,长度为扩展数组长度
	for (int i = 0; i !=s.length(); ++i)
	{
		r[i] = R > i ? MIN(r[2 * C - i], R - i) : 1; //r[i]位置的最大回文半径，最起码的结果
		while ((i + r[i])<s.length() &&( i - r[i])>=0)//再进一步看i处半径能不能继续扩，首先不越界
		{
			if (s[i + r[i]] == s[i - r[i]])//还能扩
				r[i]++;
			else//扩不了，while循环结束
				break;
		}
		if (i + r[i] > R)//某一位置的最右回文半径，超过了边界
		{
			R = i + r[i];//更新边界R
			C = i;//更新最右回文半径中心C，C伴随着R变化，R更新，C也更新；
		}
		max = MAX(r[i], max);
	}//for循环结束；
	return max-1;//原字符串的最大回文子串长度为扩展字符串的最大回文半径-1；
}

#endif 

manacher算法的扩展应用

//给定一个字符串str1，只能往str1的后面添加字符变成str2，要求str2
//整体都是回文串且最短。
//1、只要求出包含了str1中最后一个字符的最长回文子串s即可。
//2、然后将子串s在str1中之前的字符逆序添加到str1末尾即可。
//如“abc12321”，包含“1”的最长回文子串是“12321”，
//将“abc”逆序添加到“abc12321”末尾，变成“abc12321cba”，即为所求的str2。
#ifndef MANACHER_SHORTEST_END_H
#define MANACHER_SHORTEST_END_H
#include<iostream>
#include<vector>
#include<string>
#define MIN(a,b)  a<b?a:b
#define MAX(a,b) a>b?a:b
using namespace std;
//原字符串变成扩展字符串，长度为奇数
string manacherString(string s)
{
	string result = "#";
	for (int i = 0; i != s.length(); ++i)
		result = result + s[i] + "#";
	return result;
}

int manacher(string str)
{
	string s = manacherString(str);
	int R = -1;//最右回文边界
	int C = -1;//最右回文边界对应的中心，随R的更新而更新。
	vector<int> r(s.length());//每个位置的最大回文半径。
	int max = INT_MAX;//记录最大回文半径
	for (int i = 0; i != s.length(); ++i)//对每一个字符
	{
		r[i] = R > i ? MIN(r[2 * C - i], R - i) : 1;//i位置的最大回文半径，最起码的长度
		while (i + r[i] < s.length() && i - r[i] >= 0)
		{
			if (s[i + r[i]] == s[i - r[i]])//i位置的最大回文子串，还能继续往外扩；
				r[i]++;
			else //扩展不了
				break;//循环结束
		}
		if (i + r[i] > R)
			{
			R = i + r[i];
			C = i;
			}
		if (R == s.length())
		{
			max= r[i];
			break;
		}
	}
	return max-1;
}
string shortestEnd(string str)
{
	int pos = manacher(str);
	string result = str;
	for (int i = str.length()-1 - pos; i >=0; --i)
	{
		result += str[i];
	}
	return result;
}

#endif // !