题目描述

输入字符串（长度<=1000000，只包含小写字母和数字）,输出最长回文串。（若有多个回文串，则输出第一个出现的回文串。）

阳历

输入

ccbaaabbcccb

输出

baaab

---

我用的string hashing + 二分，复杂度$O(nlog_2n)$，但是为啥全T，求dalao指导

Code :

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const ll mod1 = 11451411ll, mod2 = 191988111ll, mod3 = 198244353ll;
ll fastpow(int a, int b, ll p)
{
	ll ans = 1;
	while(b)
	{
		if(b & 1)
			ans = ans * a % p;
		a = 1ll * a % p * a % p;
		b >>= 1;
	}
	return ans;
}
ll s1[N][3], s2[N][3]; // s1是正序前缀和，s2是逆序前缀和
int n;
bool check(int l, int r) // 判断[l,r]是回文串
{
	int len = r - l + 1;
	ll x = (s1[r][0] - s1[l - 1][0] * fastpow(36, len, mod1) % mod1 + mod1) % mod1;
	ll y = (s1[r][1] - s1[l - 1][1] * fastpow(36, len, mod2) % mod2 + mod2) % mod2;
	ll z = (s1[r][2] - s1[l - 1][2] * fastpow(36, len, mod3) % mod3 + mod3) % mod3;
	ll x2 = (s2[n - l + 1][0] - s2[n - l - len + 1][0] * fastpow(36, len, mod1) % mod1 + mod1) % mod1;
	ll y2 = (s2[n - l + 1][1] - s2[n - l - len + 1][1] * fastpow(36, len, mod2) % mod2 + mod2) % mod2;
	ll z2 = (s2[n - l + 1][2] - s2[n - l - len + 1][2] * fastpow(36, len, mod3) % mod3 + mod3) % mod3;
	return x == x2 && y == y2 && z == z2;
} 
int val(char ch)
{
	if('0' <= ch && ch <= '9')
		return ch - '0';
	return 11 + ch - 'a';
}
bool chk(char ch)
{
	return ('0' <= ch && ch <= '9') || ('a' <= ch && ch <= 'z');
}
string a, b;
int main()
{
	char ch = getchar();
	while(!chk(ch))
		ch = getchar();
	while(chk(ch))
	{
		a.push_back(ch);
		b.insert(b.begin(), ch);
		++n;
		ch = getchar();
	}
	for(int i = 1;i <= n;++i)
	{
		s1[i][0] = (s1[i - 1][0] * 36 + val(a[i - 1])) % mod1;
		s1[i][1] = (s1[i - 1][1] * 36 + val(a[i - 1])) % mod2;
		s1[i][2] = (s1[i - 1][2] * 36 + val(a[i - 1])) % mod3;
	}
	for(int i = 1;i <= n;++i)
	{
		s2[i][0] = (s2[i - 1][0] * 36 + val(b[i - 1])) % mod1;
		s2[i][1] = (s2[i - 1][1] * 36 + val(b[i - 1])) % mod2;
		s2[i][2] = (s2[i - 1][2] * 36 + val(b[i - 1])) % mod3;
	}
	int id = 1, len = 1;
	for(int i = 1;i <= n;++i) // 枚举以i为中点的奇数长度回文串
	{
		int l = 0, r = n;
		while(l < r)
		{
			int mid = (l + r + 1) >> 1;
			if(i - mid >= 1 && i + mid <= n && check(i - mid, i + mid))
				l = mid;
			else
				r = mid - 1;
		}
		if(check(i - l, i + l) && l * 2 + 1 > len)
		{
			len = l * 2 + 1;
			id = i - l;
		}
	}
	for(int i = 1;i <= n;++i) // 枚举以i为左半中点的偶数回文串
	{
		int l = 0, r = n;
		while(l < r)
		{
			int mid = (l + r + 1) >> 1;
			if(i - mid + 1 >= 1 && i + mid <= n && check(i - mid + 1, i + mid))
				l = mid;
			else
				r = mid - 1;
		}
		if(check(i - l + 1, i + l) && l * 2 > len)
		{
			len = l * 2;
			id = i - l + 1;
		}
	}
	for(int i = 0;i < len;++i)
		cout << a[id + i - 1];
	return 0;
}