×

# RKABOL08 - Editorial

Author: ravikiran0606
Editorialist: ravikiran0606

MEDIUM-HARD

# PREREQUISITES:

DP,STRINGS, STRINGS SUFFIX STRUCTURES

# PROBLEM:

In this problem, we need to find the number of ways to split a string S to substrings such that if there are k substrings (p1, p2, p3, ..., pk) in partition, then pi = pk-i+1  for all i (1 ≤ i ≤ k) and k is even.

# EXPLANATION:

Let n be the length of the string s. Consider the string t = s[0]s[n - 1]s[1]s[n - 2]s[2]s[n - 3]...s[n / 2 - 1]s[n / 2]. The problem can be reduced to finding the number of ways to partition string t into palindromic substrings of even length.

Proof: Let k be the total number of partitions. Let pi = pk - i + 1 = x1x2x3...xm where m denotes length of pi and xj denotes jth character of pi. The part of string t corresponding to these two partitions is x1xmx2xm - 1...xm - 1x2xmx1 which is an even length palindrome. Similarly, the converse is also true.

Dynamic programming can be used to solve the problem. Let dp[i] be the number of ways to partition t[1...i] into even length palindromes. Then, where t[j + 1...i] is an even length palindrome. Of course for odd i, dp[i] = 0.

As discussed in this blog, we can use an eertree to implement the solution. On the other hand, we can avoid the use of any suffix structure by following the algorithm described in this paper.

Complexity: O(|s|log|s|)

# AUTHOR'S SOLUTION:

Author's solution can be found here

This question is marked "community wiki".

41
accept rate: 0%

19.3k348495534

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,006
×1,880
×1,161
×346
×19
×19
×19
×14