Editorial for DMOPC '15 Contest 7 P6 - A Very Very Original Problem

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: FatalEagle

Knowledge required: data structures, string algorithms

Count the number of pairs of non-overlapping palindromic substrings of the given string.

One solution is to keep track of the number of palindromic substrings encountered so far for each index and multiply it by the number of remaining palindromic substrings.

Reminder: The input string may be up to 10^5 characters long.

Time Complexity: \mathcal{O}(N)


There are no comments at the moment.