### PROBLEM LINK:

**Author:** Sunny Aggarwal

**Tester:** Vasya Antoniuk

**Editorialist:** Pushkar Mishra

### DIFFICULTY:

Medium-Hard

### PREREQUISITES:

String Matching, Z-Algorithm, DP, Palindromes

### PROBLEM:

Given three strings S_1, S_2 and S_3, find the number of palindromic strings such that they are formed by concatenation of a substring of S_1, a substring of S_2 and a substring of S_3.

### 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 S_1, S_2 and S_3 such that they are palindromic. To explain better, let x be a substring of S_1, y be a substring of S_2 and z be a substring of S_3. 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: \mid x \mid = \mid z \mid, where \mid x \mid denotes length of x.
- Case 2: \mid x \mid > \mid z \mid.
- Case 3: \mid x \mid < \mid z \mid.

**Case 1**

What the first case tells us is that we take a substring from x from S_1, and equally sized substring z from S_3 and concatenate them with some substring y from S_2 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 S_2 are palindromic. This can be done in \mathcal{O}(N^2) 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 S_1 such that reverse(x) is a substring of S_3. To do this, we take the following steps:

- We take a string S_3' = reverse(S_3).
- Next, we consider all the suffixes of S_1.
- For a particular suffix suf, we form a new string S_z = suf+\$+S_3' (’+’ denotes concatenation and $\

character is k. This means that p = S_3[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 S_3[i-k+1..i], we store this value in an array temp\_count*. Basically, temp\_count* stores the number of palindromic strings y + p where p is a substring of S_3 that end at i^{th} position in S_3 and y is some substring of S_2. All of this is done in \mathcal{O}(N^2).

The remaning part is to calculate for each index i in S_3, the number of substrings x of S_1 such that x is also a substring of S_3 which begins at i. The count when multiplied with temp\_count* 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 \mathcal{O}(N^2). Case 3 is symmetrical to Case 2.

All in all, we have \mathcal{O}(N^2) algorithm for all cases. The overall complexity of the program is hence \mathcal{O}(N^2).

### COMPLEXITY:

\mathcal{O}(N^2) per test case.