题目：

BZOJ2565

分析：

首先看到回文串，肯定能想到Manacher算法。下文中字符串\(s\)是输入的字符串\(str\)在Manacher算法中添加了字符‘#’后的字符串 (构造方式如下)

string s = "#";

for (int i = 0; i < str.size(); i++)

{

	s += str[i];

	s += '#';

}

如果用\(maxl_i\)表示以第\(i\)个字符结尾的最长回文串的长度，\(maxr_i\)表示以第\(i\)个字符开头的最长回文串的长度，那么题目中要求的可以转化为在\(s\)中找一个位置\(i\)，满足\(s_i\)是'#'且\(maxl_i+maxr_i\)最大。在原串\(str\)中，它是两个长度分别为\(\frac{maxl_i-1}{2}\)和\(\frac{maxr_i-1}{2}\)的回文串 (要减掉额外加进去的'#'字符) 。因此，算出\(maxl\)和\(maxr\)后，就可以枚举所有'#'字符来得到答案。

怎么算\(maxl\)和\(maxr\)呢？对于一个位置\(pos\)，显然以它结尾的最长回文串的中心是一个最小的\(i\)满足\(pos-i<=p_i\) (\(p_i\)是Manacher中求出的以\(i\)为中心的回文串的“半径”)，此时\(maxr_{pos}=(pos-i)*2+1\)。那么带着单调队列从左往右扫一遍就能算出\(maxr\)，详见代码。同理，从右往左扫一遍可以算出\(maxl\)

代码：

我WA一下午，只因为局部变量没初始化……

#include <iostream>

#include <string>

using namespace std;

namespace zyt

{

	const int M = 1e5 * 2 + 10;

	int p[M];

	void manacher(const string &str)

	{

		string s = "#";

		int id = 0, right = 0;

		for (int i = 0; i < str.size(); i++)

		{

			s += str[i];

			s += '#';

		}

		for (int i = 0; i < s.size(); i++)

		{

			if (i < right)

				p[i] = min(p[id * 2 - i], right - i);

			else p[i] = 1;

			while (i - p[i] >= 0 && i + p[i] < s.size() && s[i - p[i]] == s[i + p[i]])

				p[i]++;

			if (i + p[i] > right)

				right = i + p[i], id = i;

		}

	}

	inline int abs(const int x)

	{

		return x >= 0 ? x : -x;

	}

	void mk_max(int *maxx, const int len, const bool flag)

	{

		static int q[M];

		int h = 0, t = 0;

		for (int i = 0; i < len; i++)

		{

			int pos = flag ? i : len - i - 1;

			q[t++] = pos;

			while (h < t && abs(pos - q[h]) >= p[q[h]])

				h++;

			maxx[pos] = abs(pos - q[h]) * 2 + 1;

		}

	}

	void work()

	{

		string s;

		static int maxl[M], maxr[M];

		ios::sync_with_stdio(false);

		cin >> s;

		manacher(s);

		mk_max(maxl, s.size() * 2 + 1, true);

		mk_max(maxr, s.size() * 2 + 1, false);

		int ans = 0;

		for (int i = 0; i < s.size() * 2 + 1; i += 2)

			if (maxl[i] > 1 && maxr[i] > 1)

				ans = max(ans, (maxl[i] - 1) / 2 + (maxr[i] - 1) / 2);

		cout << ans << endl;

	}

}

int main()

{

	zyt::work();

	return 0;

}

巴特西

【BZOJ2565】最长双回文串 (Manacher算法)

题目：

BZOJ2565

分析：

代码：

最新文章

热门文章