My strategy is to compute the number of palindromic substrings from index 0 to index i in a prefix sum array, and then compute the number of palindromic substrings from i+1 to strlen(N)-1 in a suffix sum array. We can then sum the products of prefix[i]*suffix[i+1] and somehow account for overcounting to get our answer. My main issue is finding the number of palindromic substrings in O(N) time (O(N^2) is not feasible as N could be up to 10^5).
Is my method reasonable, and if so, how can I solve the subproblem of finding the number of palindromic substrings in a prefix?
Please help, and thanks in advance!
See 17E - Palisection.
Here is the editorial.
You can calculate the number of palindromic substrings in every prefix and suffix in linear time after running Manacher's algorithm.
UPD: Just noticed the name of the problem: "A Very Very Original Problem". Hmmm...