SarvagyaAgarwal's blog

What is the key insight behind this problem ?
By SarvagyaAgarwal, history, 9 years ago, In English

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

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you please give a proof for the same fleimgruber.

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

    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.

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

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

      → Reply