LuoguP1723 高手过愚人节题解

Content

有 \(n\) 次询问，每次询问给定一个字符串 \(s\)，求这个字符串最长的回文子串的长度。

数据范围：\(n\) 无解（至少从题面来看是这样的），字符串长度目测应该在 \(10^7\) 范围内。

Solution

这道题目显然会要用到 manacher 算法，关于这个算法的详情可以看 \(\texttt{P3805}\) 的题解或者这篇博客，这里不再赘述了。

本题相对于 \(\texttt{P3805}\) 而言只是多了一个多组询问而已，其它的本质都是一样的。所以，直接将 \(\texttt{P3805}\) 的代码稍微改一下就可以过这道题目了。

Code

#include <cstdio>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

using namespace std;

char s[22000007], ss[22000007];

int p[22000007], n, cnt, ans;

void pre(char* s) {

	int len = strlen(s);

	ss[++cnt] = '`', ss[++cnt] = '#';

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

		ss[++cnt] = s[i];

		ss[++cnt] = '#';

	}

}

void manacher(char* s) {

	for(int t = 1, r = 0, mid = 0; t < cnt; ++t) {

		if(t <= r) p[t] = min(p[mid * 2 - t], p[mid] + mid - t);

		else	p[t] = 1;

		for(; ss[t + p[t]] == ss[t - p[t]]; p[t]++);

//		while(ss[t + p[t]] == ss[t - p[t]])	p[t]++;

		if(p[t] + t - 1 > r)	r = p[t] + t - 1, mid = t;

	}

}

int main() {

	int n;

	scanf("%d", &n);

	while(n--) {

		memset(p, 0, sizeof(p));

		cnt = ans = 0;

		scanf("%s", s);

		pre(s);

		manacher(s);

		ans = 0;

		for(int i = 0; i < cnt; ++i)	ans = max(ans, p[i]);

		printf("%d\n", ans - 1);

	}

}

巴特西

LuoguP1723 高手过愚人节题解

Content

Solution

Code

最新文章

热门文章

巴特西

LuoguP1723 高手过愚人节 题解

Content

Solution

Code

最新文章

热门文章

LuoguP1723 高手过愚人节题解