Блог пользователя SarvagyaAgarwal

Автор SarvagyaAgarwal, история, 8 лет назад, По-английски

http://www.spoj.com/problems/VPALIN/
How can Knuth-Morris-Pratt Algorithm (KMP) be used here ?

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think hashing might be a better option. Calculate forward and reverse hashes of each, then for each string, you can count how many hashes of reversed string are there.

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Notice that every palindrome (..and each string in general..) can be written by repeating some pattern. For example, "aaa" = "a" * 3, "abab" = "ab" * 2 and "aba" = "aba" * 1. We can observe that two palindromes produce a new palindrome when connected to each other, only if their repeating pattern is the same (so "aa" and "a" works, but "aa" and "aba" doesn't). To find the smallest repeating pattern KMP (or in my case the Z-Algorithm) can be used.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Can you please give a proof for the same fleimgruber.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you explain how to handle this case :- Suppose i have strings 'aba' and 'ba' , then repeating subtrings of both of them is 'aba' and 'ba' which means they are not equal but they form a valid palindrome. The question just says that the strings have to be palindrome. But in general I want to ask this.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Given strings are palindrome. So string "aba" may appear, but string "ba" won't appear.