ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1297. Palindrome

WA#12
Posted by jerry 15 Jul 2017 07:25
tried all mentioned test cases .all correct. still WA on #12.
using surfix array.any idea?

code here:

#include <cstdio>
#include <cstring>
int const N=220000;
int st[256], rank[2*N], rank1[2*N], count[N], tmp[N];
char a[N], b[N], s[N], max1;
int sa[N], height[N], si;
int main(){
    memset(st, 0, sizeof st);
    memset(rank, 0, sizeof rank);
    memset(rank1, 0, sizeof rank1);
    scanf("%s", b);
    int n1=strlen(b);
    for(int i=1; i<=n1; ++i)a[i]=b[i-1];
    for(int i=1; i<=n1; ++i)a[i+n1+1]=b[n1-i];
    a[0]=' ';
    a[n1+1]='#';
    int n=2*n1+1;
    a[n+1]='&';
    for(int i=1; i<=n; ++i)st[a[i]]=1;
    for(int i=1; i<=255; ++i)st[i]+=st[i-1];
    for(int i=1; i<=n; ++i)rank[i]=st[a[i]];

    int k=0;
    for(int p=1; k!=n; p+=p){
        memset(count, 0, sizeof count);
        for(int i=1; i<=n; ++i)count[rank[i+p]]++;
        for(int i=1; i<=n; ++i)count[i]+=count[i-1];
        for(int i=n; i>=1; --i)tmp[count[rank[i+p]]--]=i;

        memset(count, 0, sizeof count);
        for(int i=1; i<=n; ++i)count[rank[i]]++;
        for(int i=1; i<=n; ++i)count[i]+=count[i-1];
        for(int i=n; i>=1; --i)sa[count[rank[tmp[i]]]--]=tmp[i];

        memcpy(rank1, rank, sizeof rank1);
        rank[sa[1]]=k=1;
        for(int i=2; i<=n; ++i){
            if(rank1[sa[i]]!=rank1[sa[i-1]] or rank1[sa[i]+p]!=rank1[sa[i-1]+p])++k;
            rank[sa[i]]=k;
        }
    }
    k=0;
    for(int i=1; i<=n; ++i){
        if(rank[i]==1){
            k=0;
        }else{
            --k;
            if(k<0)k=0;
            while(a[i+k]==a[sa[rank[i]-1]+k])++k;
        }
        height[rank[i]]=k;
    }

    int max=-1;
    for(int i=2; i<=n; ++i){
        int p=sa[i];
        int q=sa[i-1];
        if((p-1)/n1 != (q-1)/n1){
            if(p+q+height[i]==n+2){
                if(height[i]>max){
                    max=height[i];
                    si=p;
                }
            }
        }
    }
    for(int i=si; i<si+max; ++i)printf("%c", a[i]);
    return 0;
}

THX :)
Re: WA#12
Posted by Mahilewets 15 Jul 2017 09:29
Are interesting in solving the task or in solving the task with suffix array or in knowing why your program outputs wrong at #12?

Probably third is the case...  So I tried to read your program.  Have not understand.  Maybe you elaborate details of your algorithm.
Re: WA#12
Posted by elijahqi 15 Jul 2017 12:31
You need to output the first of them if there are several such strings.But when you correct it ,i guess you 'll WA #18