If you are using int(s[i]) to get the representation for any alphabet, you may need to enlarge your counting sort table and counting sort iteration limit. I thought 200 was enough for latin alphabets, but actually I tried several times and succeeded at about 1100. I don't even know why...

Can anyone provide test case for WA#1, please?

I Got a Wrong Answer For Test 19.. Can Anyone tell what the corresponding input .. if known..

#include<stdio.h>
#include<string.h>

int main()
{
    int **a,i,j;
    int answer[2],len,n;
    char str[1001],revstr[1001];
    scanf("%s",&str);
    n=strlen(str);
    a=(int**)malloc(sizeof(int**)*n);
    for(i=0;i<n;i++)
    a[i]=(int*)malloc(sizeof(int)*n);
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    a[i][j]=0;
    strcpy(revstr,str);
    for(i=0;i<strlen(str);i++)
    revstr[i]=str[strlen(str)-i-1];
    revstr[i]='\0';
    answer[0]=0;
    answer[1]=0;
    len=0;
    for(i=0;i<strlen(str);i++)
    {
    for(j=0;j<strlen(revstr);j++)
    {
        if(str[i]!=revstr[j])
        a[i][j]=0;
        else
        {
           if(i==0||j==0)
           a[i][j]=1;
           else
           a[i][j]=1+a[i-1][j-1];
           if(a[i][j]>len)
           {
                len=a[i][j];
                answer[0]=i;
                answer[1]=j;
           }
        }
    }
    }
    for(i=answer[0]-len+1;i<=answer[0];i++)
    printf("%c",str[i]);
    return 0;
}

Edited by author 23.11.2007 01:20

Try abasajhdabba
the answer should be 'abba'

4686044    16:50:13   21 Dec 2012    Marian Darius    1297. Palindrome    C++    Accepted      0.031    108 KB

Just try iterating the middle of the palindrome and extend to both ends, until you find two elements that are different.

I got a wrong answer on 25 but I don't know why.
Is there someone could give me some tests?

My program read string S from the input and create reverse string R from the source string. Then I search in cycle with prefix function maximum suffix which may be prefix on string S.substr(i, S.length()-i)+R   i - the number of the iteration.
Then I check if the getting string the palindrome, I remember then offset and length of the string. In the end print maximum substring. Got WA on 17 test.

Thanks on the future...:)

If you're using hash-function, change your prime base, it has helped me.
P.S. I tried this numbers below:
This bases cause WA:  13, 71, 97, 313, 919, 967, 1009
And on this I got AC: 157, 2539

Edited by author 17.06.2015 23:58

#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;
}

this can be done very cool in O(N) with Suffix Trees. Try it!

try this test:
11

answer is 11, not 1

var
a:array[1..1000] of string;
S, pol:string;
N, i, j, dlina:longint;
function Sum(i, j:integer):string;
var k:string;
var i1:integer;
begin
k:='';
for i1:= i to j do
k:=k+a[i1];
Sum:=k;
end;
function Sum1(i, j:integer):string;
var k:string;
var i1:integer;
begin
k:='';
for i1:= j downto i do
k:=k+a[i1];
Sum1:=k;
end;
begin
readln(S);
N:=length(S);
for i:= 1 to N do
a[i]:=copy(lowercase(S), i, 1);
dlina:=0;
for i:= 1 to N-1 do
begin
for j:= i+1 to N do
if (Sum(i, j)=Sum1(i, j)) and (length(sum(i, j))>dlina) then
begin
pol:=Sum(i, j);
dlina:= length(sum(i, j));
end;
end;
writeln(pol);
end.

'The sample text that could be READED the same in both orders ArozaupalanalapuazorA' =)

Edited by author 10.03.2014 19:18

Edited by author 10.03.2014 19:18

bbaaabb
answer : bbaaabb

There are some AC solutions which are actually O(N^3).
Here is the test when some of them fail (3.42s):
#include <iostream>
#include <fstream>
using namespace std;

int main() {
    ofstream fout("test.txt");

    for (int i = 0; i < 1000; i++)
        fout << (char)(i%26+'a');

    return 0;
}

I have used manacher'a algorithm   and tried all the test cases discussed in these discussions and getting correct solution....
I have used manacher for even and odd palindromes separately and found the longest and if longest comes again... as in the same length..take the smaller start..
but now,... I got WA #7 ...I initially faced some problem in compilation too..please suggest some test case

P.S. : m doing while(getline(cin,string))  and also tried while(cin>>string)
is something to be done here...please suggest

Для каждого места (буквы + расстояния между ними) будем проверять длину макс подпалиндрома с помощью бин поиска (его длину).
Осталось за О(1) проверить является ли эта подстрока палиндромом, что можно сделать с помощью хешей (заранее посчитать хэш для каждого префикса, и высчитывать хэш подстроки в обе стороны и сравнивать)

I have tested for almost all test cases intentioned in discussions.
what might be the problem ?? ple help
code :
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package timusonlinejudge;

import java.util.Scanner;

/**
 *
 * @author dell
 */
public class N1297 {
    public String getPal(String s, int i, int j,String result){
        while((i>=0)&&(j<=s.length()-1)){
            if((""+s.charAt(i)).equalsIgnoreCase(""+s.charAt(j))){
                result = s.charAt(i)+result+s.charAt(j);
                i--;j++;
            }
            else{
               break;
            }
        }
        return result;
    }
    public String longestPal(String s){
       // System.out.println("---");
        if(s.isEmpty()){
            return "";
        }
        String result = s.substring(0,1);

        //System.out.println("---"+result);
        for(int i = 1; i<s.length();i++){
            if((""+s.charAt(i-1)).equalsIgnoreCase(""+s.charAt(i))){
                String temp = getPal(s,i-1,i,"");
                //System.out.println(temp);
                if(temp.length()>result.length()){
                    result = new String(temp);
                    //System.out.println(temp);
                }
            }

                String temp = getPal(s,i-1,i+1,""+s.charAt(i));
                //System.out.println(temp);
                if(temp.length()>result.length()){
                    result = new String(temp);
                    //System.out.println(temp);
                }

        }
      return result;
    }
     public static void main(String[] args) {
        N1297 main = new N1297();
        Scanner sc = new Scanner(System.in);

        String input = sc.nextLine();
        //System.out.println(input);
        System.out.println(main.longestPal(input));

        // TODO code application logic here
    }

}