SarvagyaAgarwal's blog

By SarvagyaAgarwal, history, 4 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

»
4 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.

»
4 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.

  • »
    »
    3 years ago, # ^ |
    Rev. 8   Vote: I like it 0 Vote: I do not like it

    Can you explain how to find the smallest repeating pattern using Z-algorithm? After finding the Z-array I was doing this:

    for(i = 0; i < length_of_z-array; i ++)
    {
            if(z[i]+i == length_of_z-array && i <= z[i])
            {
                   repeating_pattern = s.substr(0 , i);
                   break;
            }
        }
        if(i == s.length())
         {
           repeating_pattern = s;//whole string
       }
    
    

    What is wrong in my algorithm? I am not able to find any test case for which this algorithm fails. Please have a look to my algorithm and if possible tell me the mistake or tell your algorithm to solve this query. THANKS:).

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you please give a proof for the same fleimgruber.

  • »
    »
    5 weeks 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.