PROBLEM LINK:
Author: Sudhanshu Gupta
Tester: Sudhanshu Gupta
Editorialist: Sudhanshu Gupta
DIFFICULTY:
HARD
PREREQUISITES:
String Matching, Z-Algorithm, DP, Palindromes
PROBLEM:
Given three strings SN1, SN2 and SN3, find the number of palindromic strings such that they are formed by concatenation of a substring of SN1, a substring of SN2 and a substring of SN3.
EXPLANATION:
This problem is implementation heavy and requires certain reductions. Let’s try to simplify what the question asks for. We have to give the number of strings that we can form from substrings of SN1, SN2 and SN3 such that they are palindromic. To explain better, let x be a substring of SN1, y be a substring of SN2 and z be a substring of SN3. Then x+y+z should be palindromic (’+’ denotes concatenation operator).
To make the analysis of the problem a bit simpler, let’s divide the problem into following three cases:
Case 1: ∣x∣=∣z∣, where ∣x∣ denotes length of x
Case 2: ∣x∣>∣z∣
Case 3: ∣x∣<∣z∣
What the first case tells us is that we take a substring from x from SN1, and equally sized substring z from SN3 and concatenate them with some substring y from SN2 in the order x+y+z. For x+y+z to be a palindrome, there there are certain conditions that need to be met. These are:
x = reverse(z)
y is a palindrome in itself.
How can we get the number of possible combinations of x, y and z that fall under this case? First, let us determine how many substrings y of SN2 are palindromic. This can be done in O(N2) using the standard DP approach used for finding the longest palindromic substring of a string. Once this is done, we need to calculate then number of substrings x of SN1 such that reverse(x) is a substring of SN3
To do this, we take the following steps:
We take a string S′3 = reverse(SN3)
Next, we consider all the suffixes of SN1
For a particular suffix suf, we form a new string Sz = suf+*+S′3 ('+' denotes concatenation and * is a random character which doesn't appear in text).
We run the Z-Algorithm on Sz. The sum of values of the Z array obtained from the running of this algorithm gives us the number of substrings x of SN1 such that reverse(x) = z
Repeat for all suffixes of SN1
The running time of this part of the algorithm is also O(N2) since we have to consider N suffixes and for each one, the Z-Algorithm takes O(N) time. Once we have the count of required substrings x of SN1, we can multiply this with the number of palindromic substrings y of SN2 to get the number of strings x+y+z that fall under this case.
Case 2 and 3
The key here is to reduce this case to Case 1. Let us assume without loss of generality that ∣x∣<∣z∣. The other case is symmetrical.
For x+y+z to be a palindrome, the following conditions must hold:
x = a prefix of reverse(z)
(y + remaining part of z) forms a palindrome.
To make this clear, let’s take a case. Let x = ab, y = cda and z = dcba. We see that x is a prefix of reverse(z). Also, (y + remaining part of z), i.e., (y + dc) = cdadc forms a palindrome. Thus, x+y+z = abcdadcba is palindromic.
How do we count all such x+y+z that fall under this case? For this we first count the number of ways such that (y + a substring of p of SN3) form a palindrome (note we have taken variable p here in order to avoid confusion with z that we want in the final count). How do we go about it?
For p, we find the number of substrings y of SN2 such that y+p is a palindrome. To do this, we take S′3 = reverse(SN3). For every suffix suf of SN2, we run the Z-Algorithm on suf++S′3. Let us say that the Z value for some index i after the character is k. This means that p = SN3[i−k+1…i]. The number of required substrings y for this p is given by the number of palidromic substrings of suf such that they begin at index k+1 of the suf. How to do this?
This can be found from the same DP table as we built in Case 1. Once we have the number of y
for a particular p which is equal to SN3[i−k+1…i], we store this value in an array temp_count[i]. Basically, temp_count[i] stores the number of palindromic strings y + p where p is a substring of SN3 that end at ith position in SN3 and y is some substring of SN2. All of this is done in O(N2).
The remaning part is to calculate for each index i in SN3, the number of substrings x of SN1 such that x is also a substring of SN3 which begins at i. The count when multiplied with temp_count[i] gives the number of palindromic strings x+y+z which fall under this case. The count can be easily calculated using Z-Algorithm in the same way as in Case 1. The complexity of this part is again O(N2). Case 3 is symmetrical to Case 2.
All in all, we have O(N2) algorithm for all cases. The overall complexity of the program is hence O(N2).
SOLUTIONS:
Solution can be found here.