Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

xennygrimmato's blog

By xennygrimmato, 10 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

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

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

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

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