RKABOL08 - Editorial

PROBLEM LINK:

Practice

Contest

Author: ravikiran0606

Editorialist: ravikiran0606

DIFFICULTY:

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* 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* = 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