I solve this problem using Manacher's algorithm but I got 0.015 ms. For those people who solve this problem using a faster algorithm please tell me the name of the alg.....

Here's my code that runs well on my PC.

#include<iostream>
#include<algorithm>

using namespace std;
main()
{
      string txt;
      string txtRev;
      string tmp;
      int i;
      int com;
      while(cin>>txt){
      i=0;
      do{
        for (int n=i+2;n<txt.length();n++){
            tmp=txt.substr(i,n);
            txtRev=tmp;
            reverse(txtRev.begin(),txtRev.end());
            com= txtRev.compare(tmp);
         if (com==0) break;
         }
         i++;
      }while (com!=0);
      cout<< tmp <<" " <<endl;
      }
}

what is the 19test?

zzzdzaadzzz  answer is zzz but not zdz

I get wrong three times becase of this data..

may it can help you

Please add test

aa

I know AC solution that answers to this test 'a'.

my code can pass all my tests :

aaabbbaaa : aaabbbaaa
qwerSOMETEXTrewq : ETE
bfbaaaafbf : bfb
asdaaaafgh : aaa


why i get WA on second test?

Task on russian say "читающаяся одинаково в обоих направлениях"
But if i use toLower(), i have WA, without i have AC

In english version we have only "The longest substring with mentioned property".

even O(n^3) can pass it.......
so just enumerate it.......

I know AC solition that have TLE on the following tests:
'b', then 'a' 999 times
'a' 999 times, then 'b'

I know AC solition that have TLE on the following tests:
'b', then 'a' 999 times
'a' 999 times, then 'b'

The problem says :"the input contains a single LINE".
LINE is assumed to end with '\n' symbol,and I got TLE writing

cin.get(c);
while(c!='\n')
{...cin.get(c);}

then I changed this to
while(cin>>c) and got AC,but this kind of input ends with EOF character,NOT with '\n'!
Admins,please fix this!

It's ma prog and it works well, But I get WA at test 2...WHY???


Uses Math;
Var
  x,y:array[1..1000] of char;
  T:array[0..1000,0..1000] of integer;
  i,j,n,z,d:integer;
BEGIN
  n:=1;
  read(x[n]);
  while (not Eoln) do begin inc(n); read(x[n]); end;

  for i:=0 to n do T[0,i]:=0;
  for i:=0 to n do T[i,0]:=0;
   FOR i:=1 to n do
    FOR j:=1 to n do
     if ord(x[i])=ord(x[n-j+1]) then T[i,j]:=T[i-1,j-1]+1
                                else T[i,j]:=max(T[i-1,j],T[i,j-1]);
  d:=T[n,n]; i:=n; j:=n; z:=1;
  while (d<>0) do
    begin
      while (T[i-1,j]=d) do DEC(i);
      while (T[i,j-1]=d) do DEC(j);
      y[z]:=x[i]; INC(z);
      DEC(i); DEC(j); DEC(d);
    end;
  for i:=z-1 downto 1 do write(y[i]);
END.

Edited by author 04.12.2008 01:13

I think the answer in the current example must be :

      aplehtobeaeheaebothelpa

NOT : ArozaupalanalapuazorA

Plz look at this moment carefully !!!



Edited by author 30.11.2008 16:47

#include "iostream"
#include "string"
#include "vector"
using namespace std;
bool is_palindrom (string s,int nach,int krai) {
for (int i=nach,j=krai;i<=j;i++,j--) if (s[i]!=s[j]) return false;
return true;
}
int main () {
char ch;
string s,s1,spal;
int j=-1,mx=-1;
while (cin>>ch) {
s+=ch;
j++;
int i=-1;
string s1=s;
vector<int>a;
do {
    i++;
    if (s1[i]==ch) a.push_back(i);
}
while (i<=s1.length());
for (int i=0;i<a.size();i++)
    if (is_palindrom(s1,a[i],j)) {
                              string s2=s1.substr(a[i],j-a[i]+1);
                              int l=s2.length();
                              if (l>mx) {mx=l;spal=s2;break;}
                              }
}
cout<<spal<<endl;
system ("pause");
return 0;
}

who can give your code to me ?
  if you used suffix arry or suffix tree
  The best  used c language


email: k13795263@126.com

who can give me some test data?

My program is wa #19?

puzzling ?

You must have found the longest common substring of a and rev(a). That method works. But you should also be taking care of false positives like
rewqSOMETEXTqwer. You get rewq while ETE is the answer. So, once you think it's the end of a possible palindrome, have a checker to make sure that IT IS a palindrome and not a false positive sign.
This is the part of my code which does this(I've used the dp method found in wikipedia)
              if(mxLen<lcs[i][j])
              {

                   if(((i==n || j==n) || a[i]!=b[j]))
                      if(checkIfPali(a, i-1, lcs[i][j]))
                                 {
                                  mxPt=j-1;
                                  mxLen=lcs[i][j];
                                 }
              }

Hope this helps many,
Jagat

I got wrong answer for test #11 for the follwing code ......
can anybody tell the error in this code.....


#include <stdio.h>

void isPalendrome(char check[]);
int flag1 = 0;

main()
{
    int i,j,k=1,l,len,upper_limit,lower_limit,n;
    char string[1001],check[1001];
    scanf("%s", string);
    n = strlen(string);
    len = n-1;
    isPalendrome(string);
    while(flag1==0&&len>0)
    {
        k++;
    lower_limit=0;
    for(i=0;i<k;i++,lower_limit++)
      {
        for(j=lower_limit;j<len;j++)
            check[j] = string[j];
        isPalendrome(check);
        if(flag1==1)
            break;
       }
      upper_limit = n-1;
      if(flag1==0)
       {
        for(i=0;i<k;i++,upper_limit--)
        {
            for(j=upper_limit,l=len-1;l>=0;j--,l--)
               check[l] = string[j];
            isPalendrome(check);
            if(flag1==1)
            break;
        }
        }
      len--;
      check[len] ='\0';
    }

 }


void isPalendrome(char check[])
{
    int len,i,j,flag2=0;
    len = strlen(check);
    j = len-1;
    len = len/2;
    for(i=0;i<len;i++,j--)
    {
        if(check[i]!=check[j])
           {
                flag2 = 1;
                break;
           }
    }
    if(flag2==0)
        {
            flag1 = 1;
            printf("%s",check);
            scanf("%s",check);
            return;
        }
    else
       return;
}

program Bourne;
  var
    x:char;
    a:array[1..1000] of char;
    n,i,start,len,maxlen:integer;
  procedure find(p,q:integer);
    var
      p0,q0:integer;
    begin
      p0:=p;  q0:=q;
      while (p0>=1)and(q0<=n)and(a[p0]=a[q0]) do
        begin
          inc(len,2);
          inc(q0); dec(p0);
        end;
      if len>maxlen then
        begin
          maxlen:=len;
          start:=p0;
       end;
    end;
  begin
    n:=0;
    repeat
      read(x);
      inc(n);
      a[n]:=x;
    until eoln;
    maxlen:=0;
    for i:=1 to n do
      begin
        len:=0;
        find(i,i+1);
        len:=1;
        find(i-1,i+1);
      end;
    for i:=1 to maxlen do
      write(a[start+i]);
    writeln;
  end.