PROBLEM LINK:Author: ravikiran0606 DIFFICULTY:MEDIUMHARD 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_{1}, p_{2}, p_{3}, ..., p_{k}) in partition, then p_{i} = p_{ki+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_{1}x_{2}x_{3}...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_{1}x_{m}x_{2}x_{m  1}...x_{m  1}x_{2}x_{m}x_{1} 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(slogs) AUTHOR'S SOLUTION:Author's solution can be found here
This question is marked "community wiki".
asked 14 Mar, 01:16
