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
    }

}

I don't know why this solution is correct, but it got accepted.
I thought that this solution will get TL.
Author of problem: easy tests?

Who couldn't find solution try to understand this code:

#include<map>
#include<cmath>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<string.h>
//#include<windows.h>
#include<algorithm>
#define y1 abcde
#define sqr(x) ((x)*(x))
#define INF 20000000000000000
using namespace std;

   string s;
   int i,n,ans,j,l,r;

   bool check(int l,int r)
{
        for(int i = 0; i < (r - l + 1) / 2; i++)
        if (s[l+i] != s[r-i]) return false;
    return true;
}
int main()
{
   //srand(GetTickCount());
   #ifndef ONLINE_JUDGE
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
   #endif

    cin>>s;
    n = s.size(); i++; s = '#' + s;
    for(i = 1; i <= n; i++)
     for(j = i; j <= n; j++)
    {
             if (check(i,j))
              if (j - i + 1 > ans)
                   ans = j-i+1,
                   l = i,
                   r = j;
    }
     for(i = l; i <= r; i++) cout<<s[i];
    return 0;
}

Edited by author 13.02.2013 14:44

Edited by author 13.02.2013 14:45

Input: abc
Expected output: a

My program was failing test 2 because I was not initialing correctly and so returned b for this case. Just in case any one else has this problem.

I'm happy that i solved it! I'm think it is a basis of programming, that's why I'm happy!
There is no english.. only runglish.. I'm Sorry for this, but it is so cool!

This is hint: maximal substring-palindrome is maximal common substring of given string and reversed string => You can solve it for O(N^2).
The second variant - trivial dynamic. dp[l][r] = answer for substring from l to r. Sorry for my poor english(((

Edited by author 13.11.2012 23:38

AC!!!! :D

Don't use overflowing (int64 or int) in your hash function! :D


Edited by author 10.08.2012 18:07

#include<iostream>
#include<string>

using namespace std;

int isPalindrom(string);

int main(void){
    string s,s1,s2;
    int i,j,k;
    cin>>s;
    k=0;
    for(i=0;i<s.size();i++)
        for(j=1;j<=s.size();j++)
            if(isPalindrom(s.substr(i,j))){
                s1=s.substr(i,j);
                if(s1.size()>k){
                    k=s1.size();
                    s2=s1;
                }
            }
    cout<<s2;
return 0;
}

int isPalindrom(string s){
     int i,flag;
     for(i=0;i<s.size()/2;i++)
         if(s[i]!=s[s.size()-i-1]){
             flag=0;
             break;
         }
         else
             flag=1;
    if(flag)
        return 1;
    else
        return 0;
}

What is test 1?
I have even tried out.println('ArozaupalanalapuazorA'); but no luck.

const
  ma=1000;
type
  strin=array[1..ma] of char;
  zx=record
     a,x,y:integer;
     end;
var
  a:strin;
  i,j,c,k:integer;
  max:zx;
function  check(i,j:integer):boolean;
var asd,q:integer;
label poz;
begin
   asd:=j-i;
   for q:=i to i+((j-i) div 2) do
   begin
       if a[q]<>a[j-(q-i)] then
       begin
           check:=false;
           goto poz;
       end;
   end;
   check:=true;
   poz:
end;
begin
  {assign(Input,'input.txt'); assign(output,'output.txt');
  reset(Input);              rewrite(Output);}
  i:=0;
  while not eoln do
  begin
    inc(i);
    read(a[i]);
  end;
  k:=i;

  c:=i-j;
  for i:=k downto 2 do
  for j:=i downto 1 do
  begin
    if (check(j,i)) and ((i-j)>=max.a) then begin max.a:=i-j;  max.x:=j; max.y:=i; end;
  end;
  for i:=max.x to max.y do write(a[i]);
  writeln;
{  close(Input);              close(Output);}
end.

I use DP to find the max substring of the input and its reverse, but I keep getting WA 11... Did anyone else got WA 11? If so, how did you fix it? Thanks in advance :)

Is there something special in test #23? I got crash (access violation).