xennygrimmato's blog

Longest common palindromic substring
By xennygrimmato, 12 years ago, In English

Given two strings, what is the best method to find the longest common palindromic substring?

This problem was asked in a local programming competition in my city, constraints were not specified.

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

»
12 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

Manacher's algorithm. Also you can use hashes + binary search or suffix structures.

→ Reply
»
12 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

We can do it in O(N*logN), you can find it here

→ Reply