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

F[i]: the longest Palindrom ended at St[i]
Cont[i]: the number of continue same characters with St[i], ended at St[i]

if St[i] = St[i - F[i - 1] - 1] then
  F[i] = F[i - 1] + 2
else
  if St[i] = St[i - 1] then
    F[i] = Cont[i];

The result is Max(F)

What's wrong with it ???

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

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

Some new tests were added. 76 authors lost AC.
By the way, if your AC solution is slow and you know the worst-case test, you can write it in the webboard, and we'll add it to the testset.

Please help me!

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 think my code is correct..
what's the tricky input? or what's wrong with my code?
I just made a O(n^2) algorithm to search
here is my code:
#include <stdio.h>
#include <string.h>
char a[1003],b[1003];

int main(){
  int i,j,u,v,l,ind,res=0,tmp;
  scanf("%s",&a);
  l=strlen(a);
  for(i=0;i<l;i++)
    b[i]=a[l-1-i];
  for(i=0;i<l;i++)
    for(j=0;j<l;j++)
      if(a[i]==b[j]){
         tmp=0;
         for(u=i+1,v=j+1;v<l;u++,v++){
            if(a[u]==b[v])
              tmp++;
            else
              break;
         }
         if(tmp>=res){
           res=tmp;
           ind=i;
         }
     }
   for(i=ind;i<=ind+res;i++)
      printf("%c",a[i]);
   printf("\n");
  return 0;
}

Plz help me, or give some test.

var
  st:array[1..1000] of integer;
  b,e,i,j,k,m,max,n,ist:integer;
  a:array[1..1000] of char;
  ch:char;

procedure readdata;
begin
  n:=0;
  while not eof do
  begin
    inc(n);
    read(ch);
    a[n]:=ch;
  end;
end;

procedure writedata;
begin
  for i:=b to e-1 do
  write(a[i]); writeln(a[e]);
end;

procedure push(x:integer);
begin
  st[ist]:=x;
  inc(ist);
end;

procedure pop(var x:integer);
begin
  dec(ist);
  x:=st[ist];
  st[ist]:=0;
end;

begin
  readdata;
  max:=0; ist:=1;
  for i:=1 to n-1 do
  begin
    j:=i;
    if (ist>=2) and (a[j]=a[st[ist-1]]) then
    begin
      k:=0; m:=ist-1;
      while (j<=n) and (m>=1) and (a[j]=a[st[m]]) do
      begin
        inc(j);
        dec(m);
        inc(k);
      end;
      k:=k*2;
      if k>max then
      begin
        max:=k;
        b:=m+1;
        e:=j-1;
      end;
      push(i);
    end                    else

    if (ist>=2) and (a[j+1]=a[st[ist-1]]) then
    begin
      inc(j);
      k:=0; m:=ist-1;
      while (j<=n) and (m>=1) and (a[j]=a[st[m]]) do
      begin
        inc(j);
        dec(m);
        inc(k);
      end;
      k:=k*2+1;
      if k>max then
      begin
        max:=k;
        b:=m+1;
        e:=j-1;
      end;
      push(i);
    end          else push(i);

  end;
  writedata;
end.

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.

Why I always get TL(1.015) in test #14?

Why i always get TL(1.015) in test #14?

How can we read, not using CRT and ASM???
I have truest solution, but can not read more then 255 of char!!!

Edited by author 15.09.2004 21:40

Edited by author 15.09.2004 21:41

{$APPTYPE CONSOLE}
Var
  S,st:AnsiString;
  i,N,d,MaxLen:Integer;
begin
  Readln(S);
  N:=length(S); MaxLen:=0;
  for i:= 1 to N do begin
    d:=0;
   while (i>=d)And((N-i)>=d)And(S[i-d]=S[i+d])do Inc(d);
    if d>MaxLen then begin
      MaxLen:=d;
      st:=Copy(S,i-d+1,d*2-1);
    end;
  end;
  writeln(st);
end.

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