vamaddur's blog

Number of Pairs of Non-Intersecting Palindromic Substrings in a String
By vamaddur, history, 7 years ago, In English

Problem Link

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!

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

»
7 years ago, # |
← Rev. 2   Vote: I like it +29 Vote: I do not like it

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...

→ Reply