【POJ 3974】Palindrome

http://poj.org/problem?id=3974

Manacher模板题。Menci的博客讲得很好

有一点：Menci的代码中的right我感觉是代表能延伸到的最右端点的右边的点，因为r(i)表示包括中心点的回文半径。

不知道理解有没有错误，如果神犇发现了我的理解的错误请告诉本蒟蒻qwq

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 1000003;

int len, r[N << 1];

char c[N], s[N << 1];

void pre() {

	int clen = strlen(c);

	len = 0;

	s[++len] = '!';

	s[++len] = '#';

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

		s[++len] = c[i], s[++len] = '#';

	s[++len] = '&';

}

int cas = 0;

void Manacher() {

	int ans = 0, mid = 0, right = 1, x;

	for (int i = 1; i <= len; ++i) {

		if (i >= right) x = 1;

		else x = min(r[(mid << 1) - i], right - i);

		while (s[i - x] == s[i + x]) ++x;

		ans = max(ans, r[i] = x);

		if (i + x > right) right = i + x, mid = i;

	}

	printf("Case %d: %d\n", ++cas, ans - 1);

}

int main() {

	while (scanf("%s", c), memcmp(c, "END", 4) != 0) {

		pre();

		Manacher();

	}

}

巴特西

【POJ 3974】Palindrome

最新文章

热门文章