ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1297. Palindrome

why it wrong at Test11？
Posted by 116040179 29 Jul 2013 12:10
#include <stdio.h>
#include <string.h>
#include <string>
#include <algorithm>
using namespace std;
#define maxn 2000010

int wa[maxn],wb[maxn],wv[maxn],wss[maxn];
int rank[maxn],height[maxn];
int sa[maxn],r[maxn];
char str[maxn];
char temp[maxn];

int cmp(int *r,int a,int b,int l)
{
return r[a]==r[b]&&r[a+l]==r[b+l];
}

void da(int *r,int *sa,int n,int m)
{
int i,j,p,*x=wa,*y=wb,*t;
for(i=0; i<m; i++) wss[i]=0;
for(i=0; i<n; i++) wss[x[i]=r[i]]++;
for(i=1; i<m; i++) wss[i]+=wss[i-1];
for(i=n-1; i>=0; i--) sa[--wss[x[i]]]=i;
for(p=1,j=1; p<n; j*=2,m=p)
{
for(p=0,i=n-j; i<n; i++) y[p++]=i;
for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;
for(i=0; i<n; i++) wv[i]=x[y[i]];
for(i=0; i<m; i++) wss[i]=0;
for(i=0; i<n; i++) wss[wv[i]]++;
for(i=1; i<m; i++) wss[i]+=wss[i-1];
for(i=n-1; i>=0; i--)
sa[--wss[wv[i]]]=y[i];
for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++ )
x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}

void calheight(int *r,int *sa,int n)
{
int i,j,k=0;
for(i=1; i<=n; i++)
rank[sa[i]]=i;
for(i=0; i<n; height[rank[i++]]=k)
for(k?k--:0,j=sa[rank[i]-1]; r[i+k]==r[j+k]; k++);
}

int main()
{
while(scanf("%s",str)!=EOF)
{
int i;
int len1=strlen(str);
strcpy(temp,str);
reverse(temp,temp+len1);
//printf("%s\n",temp);
memset(sa,0,sizeof(sa));
memset(r,0,sizeof(r));
memset(rank,0,sizeof(rank));
memset(height,0,sizeof(height));
str[len1]='#';
for(i=len1+1;i<1+len1*2;i++) str[i]=temp[i-len1-1];
str[i]='\0';
for(i=0;str[i]!='\0';i++) r[i]=str[i];
da(r,sa,i+1,256);
calheight(r,sa,i);
int k=0,n=i,max=-1;
for(i = 2; i <= n; ++ i)
if((sa[i]<len1)^(sa[i-1]<len1))
if(k<height[i]){
k=height[i];
max=i;
}
else if(k==height[i]){
//    printf("i=%d max=%d\n",sa[i],sa[max]);
if(sa[max]>sa[i]) max=i;
}
i=sa[max];
for(;i<sa[max]+k;i++)
printf("%c",str[i]);
printf("\n");
}
return 0;
}
Re: why it wrong at Test11？
Posted by sarvin 27 Dec 2014 23:25
try this test case:
aabcc
output should be:aa
my program was also getting WA on test case 11,when i corrected the program for this test case,it got accepted.I hope it helps you.Thank you.

Edited by author 27.12.2014 23:33

Edited by author 27.12.2014 23:33

Edited by author 27.12.2014 23:36