Rupai's blog

SPOJ EPALIN TLE
By Rupai, 12 years ago, In English

http://www.spoj.pl/problems/EPALIN/

I use KMP. First generate failure function reverse of the string that given to me, then do KMP search to find largest suffix of the string that match with the prefix of the reverse string.

But I am not able to find anything wrong in my implementation. Can anybody please tell me why it's getting TLE??? Below is my cpp source code:

Edit: Got AC
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You've just need to find Prefix function of last character of string rstr + # + str, let it be PR, and then output str and first len - PR chars of str in reverse order.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain little bit more??? I didn't get your point :(

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Let's make string s = rstr + # + str, where str is given string, rstr is reversed str. You can take every char on the place of "#", the main thing that this char was not in str. Then compute prefix function of it, then we just need take last value PR in array, this number will show length of the longest suffix of str, which is palindromic. One can prove it. Next step of algorithm is obvious: output str and first len - PR in reverse order as I alredy said.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you very much. Now I got AC :)

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          I'm happy to help :)

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I have also used same logic as described by you but still I am getting WA for EPALIN. Here is my source code: http://pastebin.com/HanhzYZs Do you find any flaw in it ?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              11 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Hey I'm using the same logic. Where are we going wrong ?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                11 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                AC.. A slight mistake ! Debugging was fun

                → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

help... getting WA any corner cases.... https://ideone.com/EknGW8

thanku

→ Reply