C++14(g++5.4) 解法, 执行用时: 321ms, 内存消耗: 5376K, 提交时间: 2018-08-05 16:24:49

#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

const ull P = 19260817;
const int maxn = 200000 + 9;

ull H[maxn], _H[maxn], Pow[maxn];
int T, N;
string S;

ull Hash(int l, int r, ull h[]) {// [l, r)
	return h[l] - h[r] * Pow[r - l];
}

bool ok(int x, int s, int d) {
	return Hash(x + s, x + d + 1, H) == Hash(2 * N - 1 - (x - s), 2 * N - (x - d), _H);
}

int main() {
	
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	
	Pow[0] = 1;
	for(int i = 1; i < maxn; i++) {
		Pow[i] = Pow[i - 1] * P;
	}
	cin >> T;
	while(T--) {	
		cin >> S;
		N = S.size();
		S.resize(2 * N);
		for(int i = 0; i < N; i++) {
			S[i + N] = S[i];
		}
		H[2 * N] = _H[2 * N] = 0;
		for(int i = 2 * N - 1; i >= 0; i--) {
			H[i] = H[i + 1] * P + S[i];
			_H[i] = _H[i + 1] * P + S[2 * N - 1 - i];
		}
		int ans = 1, n = (N - 1) / 2;
		for(int i = n; i + n < 2 * N; i++) {
			int s = 0, l = 0, r = n;
			while(l < r) {
				int m = (l + r + 1) >> 1;
				ok(i, s, m) ? l = m : r = m - 1;
			}
			if(l + 2 >= n) {
				ans = 2 * n + 1;
				break;
			}
			s = l = l + 2, r = n;
			while(l < r) {
				int m = (l + r) >> 1;
				ok(i, s, m) ? l = m + 1 : r = m;
			}
			if(l >= n) {
				ans = 2 * n + 1;
				break;
			}
			s = ++l, r = n;
			while(l < r) {
				int m = (l + r) >> 1;
				ok(i, s, m) ? l = m + 1 : r = m;
			}
			ans = max(ans, (l - !ok(i, s, l)) * 2 + 1);
		}
		cout << ans << endl;
	}
	
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 236ms, 内存消耗: 5216K, 提交时间: 2018-08-21 01:50:53

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

typedef unsigned long long ull;

const int maxn = 100005;
const int seed=1e9+7;

int n,m;
char str[2*maxn];
ull has[2*maxn],rhas[2*maxn],pw[2*maxn];

void init()
{
	pw[0]=1;
	for(int i=1;i<=2*maxn;++i)
	{
		pw[i]=pw[i-1]*seed;
	}
}

void init_has()
{
	for(int i=1;i<2*n;++i)
	{
		has[i]=has[i-1]*seed+(str[i]-'a'+1);
	}
	rhas[2*n+1]=0;
	for(int i=2*n;i>0;--i)
	{
		rhas[i]=rhas[i+1]*seed+(str[i]-'a'+1);
	}
}

bool check_has(int a,int b,int c)
{
	ull sum,rsum;
	rsum=rhas[b]-rhas[b+c]*pw[c];
	sum=has[a]-has[a-c]*pw[c];
	return rsum==sum;
}

int check(int a,int b,int c)
{
	int ret=0;
	for(int i=0;i<3;++i)
	{
		int l,r,mid,cnt=0;
		l=1,r=c;
		while(l<=r)
		{
			mid=(l+r)>>1;
			if(check_has(a,b,mid))
			{
				l=mid+1;
				cnt=mid;
			}
			else
			{
				r=mid-1;
			}
		}
		ret+=cnt;
		if(cnt==c)break;
		c-=cnt+1;
		a-=cnt+1;
		b+=cnt+1;
		if(c<0)break;
		if(i<2)ret++;
	}
	return ret;
}

int main()
{
	int T;
	cin>>T;
	init();
	while(T--)
	{
		cin>>str+1;
		n=strlen(str+1);
		for(int i=n+1;i<=2*n;++i)
		{
			str[i]=str[i-n];
		}
		init_has();
		int ans=1;
		for(int i=n/2+1;i+n/2<=2*n;++i)
		{
			int x=(n-1)/2;
			x=check(i-1,i+1,x);
			ans=max(ans,x*2+1);
		}
		cout<<ans<<endl;
	}
}