Hotaru's problem

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 3878    Accepted Submission(s): 1271 Problem Description Hotaru Ichijou recently is addicated to math problems. Now she is playing with N-sequence. Let's define N-sequence, which is composed with three parts and satisfied with the following condition: 1. the first part is the same as the thrid part, 2. the first part and the second part are symmetrical. for example, the sequence 2,3,4,4,3,2,2,3,4 is a N-sequence, which the first part 2,3,4 is the same as the thrid part 2,3,4, the first part 2,3,4 and the second part 4,3,2 are symmetrical. Give you n positive intergers, your task is to find the largest continuous sub-sequence, which is N-sequence.   Input There are multiple test cases. The first line of input contains an integer T（T<=20）, indicating the number of test cases.  For each test case: the first line of input contains a positive integer N（1<=N<=100000）, the length of a given sequence the second line includes N non-negative integers ,each interger is no larger than  109  , descripting a sequence.   Output Each case contains only one line. Each line should start with “Case #i: ”,with i implying the case number, followed by a integer, the largest length of N-sequence. We guarantee that the sum of all answers is less than 800000.   Sample Input 1 10 2 3 4 4 3 2 2 3 4 4   Sample Output Case #1: 9   Author UESTC   Source 2015 Multi-University Training Contest 7   Recommend wange2014   |   We have carefully selected several similar problems for you:   6193  6192  6191  6190  6189  两个回文串之间有重叠的部分而已，跑一遍manacher后枚举即可。 #include <iostream> #include <cstdio> #include <cmath> #include <cstring> using namespace std; const int maxn = 1e5+50; int i,j,k,n,id,ans,cnt; int s[maxn<<1],a[maxn<<1]; void init(){ scanf("%d",&n); s[0] = -1; //这里一定要跟其他新添加的非原串字符相同，不然样例都过不了。。。 cnt = 0; for (i=0; i<n; i++) {scanf("%d",&s[++cnt]); s[++cnt]= -1;} cnt++; } void manacher(){ ans = 0; id = 0; memset(a,0,sizeof(a)); int mx = 0; for (i=0; i<cnt; i++) { if (mx>i) a[i] = min(a[id*2-i],mx-i); else a[i] = 1; while (s[i-a[i]]==s[i+a[i]]) a[i]++; if (mx<i+a[i]) {id = i; mx = a[i] + i;} } for (i=0; i<cnt; i+=2) for (j=ans; j<a[i]; j+=2){ if (a[i+j]>j) ans = j; } } int main(){ int T; cin >> T; for (int Case=1; Case<=T; Case++) { init(); manacher(); printf("Case #%d: %d\n",Case,ans*3/2); } return 0; }