LA 4975(Casting Spells-manacher+暴力查找)

4975 - Casting Spells

Time limit: 3.000 seconds 

Casting spells is the least understood technique of dealing with real life. Actually, people find it quite hard to distinguish between a real spells like ``abrahellehhelleh" (used in the battles and taught at the mage universities) and screams like ``rachelhellabracadabra" (used by uneducated witches for shouting at cats).

Finally, the research conducted at the Unheard University showed how one can measure the power of a word (be it a real spell or a scream). It appeared that it is connected with the mages' ability to pronounce words backwards. (Actually, some singers were burned at the stake for exactly the same ability, as it was perceived as demonic possession.) Namely, the power of a word is the length of the maximum subword of the form wwRwwR (where w is an arbitrary sequence of characters and wR is w written backwards). If no such subword exists, then the power of the word is 0. For example, the power of abrahellehhelleh is 12 as it contains hellehhelleh and the power of rachelhellabracadabra is 0. Note that the power of a word is always a multiple of 4.

Input 

The input contains several test cases. The first line of the input contains a positive integer Z

40, denoting the number of test cases. Then Z test cases follow, each conforming to the format described below.

The input is one line containing a word of length at most 3 . 105, consisting of (large or small) letters of the English alphabet.

Output 

For each test case, your program has to write an output conforming to the format described below.

You should output one integer k being the power of the word.

Sample Input 

2 
abrahellehhelleh 
rachelhellabracadabra
      

Sample Output 

12 
0
      

這題先用manacher得到每個字元的半徑，然後再找這個串的半邊還是回文串的回文串

LRJ說這題要用特别的資料結構，我的RMQ逾時，暴力過了。。。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define MAXN (300000+10)
#define MAXSTR (MAXN*2+2)
#define MAXLog (21)
#define Sp_char1 ('*')
#define Sp_char2 ('_') 
typedef long long ll;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
class manacher
{
public:
	int n;
	char s[MAXN];
	int p[MAXSTR];
	manacher(){n=0; MEM(s) MEM(p)}
	manacher(char *_s){n=0; MEM(s) if (_s) memcpy(s,_s,sizeof(char)*(strlen(_s)+1)),n=strlen(s); MEM(p)}
	void mem(char *_s){n=0; MEM(s) if (_s) memcpy(s,_s,sizeof(char)*(strlen(_s)+1)),n=strlen(s); MEM(p)}
	char str[MAXSTR];
	void work()
	{
		str[0]=Sp_char1;
		Rep(i,n) str[2*i+1]=Sp_char2,str[2*i+2]=s[i]; 
		str[2*n+1]=Sp_char2; str[2*n+2]='\0';
		
		n=2*n+2; MEM(p) 
		int mx=0,id=0;
		For(i,n-1) 
		{
			if (i<mx) p[i]=min(p[2*id-i],mx-i);
			
			while(str[i-p[i]]==str[i+p[i]]) ++p[i];
			if (mx<i+p[i]) //mx為已查明的最右端 
			{
				mx=i+p[i];
				id=i;
			}
		}
	}
}S;
int T;
char s[MAXN];
int main()
{
	freopen("la4975.in","r",stdin);
//	freopen(".out","w",stdout);
	
	cin>>T;
	while(T--)
	{
		scanf("%s",s);
		S.mem(s);
		S.work();
		
	//	printf("%s",S.str); 
	//	Rep(i,S.n) cout<<S.str[i]<<':'<<i<<' ';
		
		int ans=0;
				
		for(int i=1;i<=S.n-1;i+=2)
		{
			if (S.p[i]==1) continue;
			
			for(int l = (S.p[i]-1)/4*4 ; l>ans ; l-=4)
			{
				if (S.p[i-l/2]>=l/2&&S.p[i+l/2]>=l/2)
					ans=max(ans,l);
			}
			
		}
		cout<<ans<<endl; 
	}
		
	return 0;
}