#include <iostream>
#include <vector>
#include <math.h>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
   long long m,h = 0,i,t,l,n,f;
   string a,s;
   cin >> a;
   s = a;
   for(i = a.length()-1 ;i >= 0 ;i--)
   s[h] = a[i],h++;

    f = s.length()-2;
    i = 0;
    n = f;

    while(n >= 1 && m != 0)
     {
        t = n;
        m = 0;
       while(i <= n - (n  / 2) - 1)
     {
         if(s[i] != s[t])
       {
          m = 1;
          break;
       }
        i++;
        t--;
     }
         n--;
         i = 0;
     }
        if(m == 0)
         n++;
       for(i = 0 ;i < a.length() ;i++)
        cout << a[i];
       for(i = n + 1 ;i < s.length() ;i++)
        cout << s[i];
        cout << endl;
    return 0;
}

Could anyone tell me test #20?

Anyone had the same problem? please give a hint!!

Hi,

I am using a very naive algorithm to solve this problem and that's getting TL on later test cases. Can someone tell the name of the efficient algorithm which we can use for this problem ?

Thanks

I used pascal strings and got AC.

But the test data on SPOJ is wrong.

Just find the biggest polindrom, which ends in the end of s1 and so s2 is a part at the beginnig of the s1 (which is not a part of a palindrom) written backwards.

Can sb send test 5 and ans?

I think the question for some day, but I can`t solve....

please give hint.....

Edited by author 26.08.2008 05:22

These tests helped me very much. I hope it will help you.

2101221012 and answer is 210122101221012 (in test#4)
122212221 answer is 1222122212221 (in test#8)

Help plz!
I used hash,and got a WA at #21!

I used in my program

char a[10000];
cin>>a;

after I used
char a[10001];
cin>>a;

and got AC

I've got AC constructing suffix tree (mcc algo). Now, who also has O(N) solution simplier than mine, please tell me your idea. And is O(N*N) anough to get AC? Thanks.

Check your vars for type overflow (if KMP check the type of array of pr)

Edited by author 02.07.2009 21:24

A limitation of 10000 is weak. My "stupid" O(n^2) PASCAL solution gets AC in 0.078 sec.
It works very fast even on its worth test:
aaaa....aaaab (9999 letters 'a')
where it makes 9999 iterations with = and Delete() with strings of length 10000.

But actually I don't know how to change this. If just increase  limitation, even correct solutions gets WA...

my idea for solution
  k := 2;
  n := length(s);
  s1 := s[1];
  while true do begin
    i := 0;
    while (n - i >= k + i) and (s[k + i] = s[n - i]) do inc(i);
    if n - i <= k + i
    then begin
      write(s + s1);
      halt;
    end;
    s1 := s[k] + s1;
    inc(k);
  end;

excuse my english first.

i tried my program on a lot of examples of mine and it's ok.
but i got for 10 times WA on the test #4...why?

can anybody tell me what's about or give me some hint for this problem?

thx all

WA#4
program Palindome. Again Palindome;
var
    a:array [1..20010] of char;
    i,j,k,n,w:integer;
    r:char;
    s:string;
    f:boolean;
    g:text;
    t:integer;
procedure solve;
label 1;
var e:integer;
begin
     f:=false;
     t:=0;
     for k:=1 to n+i do
     if (a[k]<>a[n+i-k+1]) then goto 1;
     f:=true;
     1:
end;
    {IMPORTANT PART}
Begin
      assign(g,'input.txt');
      reset(g);
      while not eof(g) do
      begin
          readln(g,s);
          n:=0;
          for i:=1 to length(s) do
              begin
                  n:=n+1;
                  a[n]:=s[i];
              end;
              i:=0;
       repeat
                solve;
                if not(f) then
                begin
                     i:=i+1;
                     for j:=n+i downto n+1 do
                       begin
                            a[j]:=a[j-1];
                       end;
                  a[n+1]:=a[i];
                  solve;
                end;
        until f;
    end;
        close(g);
          for j:=1 to n+i do
               write(a[j]);
               readln;readln;
end.
THANKS ALL RIGHT