YouKn0wWho's blog

By YouKn0wWho, 5 years ago, In English

Let's say we have to find the number of ways to partition a string into palindromic substrings of even length. We can solve this problem in $$$O(n log n)$$$ using Palindromic tree where we have to use an extended version of the palindromic tree consisting of series links. You can solve this beautiful problem using this idea.

But then I found out that if the question would have asked for the number of ways to partition a string into palindromic substrings of length $$$l$$$ such that $$$l \bmod p <= r$$$, then I couldn't solve it.

So here I am, asking you, is there any kind of generalized solution for this kind of problem? Maybe we can solve this problem for some small $$$p$$$?

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

»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Huh, what a ridiculous statement. Where did you find it?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't find it anywhere. I have just thought about the problem.