http://www.spoj.com/problems/VPALIN/

How can Knuth-Morris-Pratt Algorithm (KMP) be used here ?

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3669 |

3 | apiadu | 3397 |

4 | TLE | 3374 |

5 | Um_nik | 3358 |

6 | 300iq | 3317 |

7 | maroonrk | 3232 |

8 | Benq | 3230 |

9 | LHiC | 3229 |

10 | 1919810 | 3203 |

# | User | Contrib. |
---|---|---|

1 | antontrygubO_o | 191 |

2 | Errichto | 185 |

3 | tourist | 182 |

4 | vovuh | 170 |

5 | pikmike | 169 |

6 | Radewoosh | 164 |

7 | ko_osaga | 162 |

8 | Um_nik | 161 |

9 | 300iq | 156 |

10 | rng_58 | 154 |

http://www.spoj.com/problems/VPALIN/

How can Knuth-Morris-Pratt Algorithm (KMP) be used here ?

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/31/2020 03:01:50 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

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.

`Can you explain how to find the smallest repeating pattern using Z-algorithm?`

`After finding the Z-array I was doing this:`

`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:).Can you please give a proof for the same fleimgruber.

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.