RKABOL08 - Editorial

[ravikiran0606]

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 (p₁, p₂, p₃, …, p_k) in partition, then p_i = p_k-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 p_i = p_{k - i + 1} = x₁x₂x₃…x_m where m denotes length of p_i and x_j denotes jth character of p_i. The part of string t corresponding to these two partitions is x₁x_mx₂x_m - 1…x_m - 1x₂x_mx₁ 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