You are not logged in. Please login at www.codechef.com to post your questions!

×

PALSTR - Editorial

PROBLEM LINK:

Practice
Contest

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 $\$$ is a random character which doesn't appear in text).
  • We run the Z-Algorithm on $S_z$. The sum of values of the $Z$ array obtained from the running of this algorithm gives us the number of substrings $x$ of $S_1$ such that $reverse(x)$ = $z$.
  • Repeat for all suffixes of $S_1$.

The running time of this part of the algorithm is also $\mathcal{O}(N^2)$ since we have to consider $N$ suffixes and for each one, the Z-Algorithm takes $\mathcal{O}(N)$ time. Once we have the count of required substrings $x$ of $S_1$, we can multiply this with the number of palindromic substrings $y$ of $S_2$ 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 $\mid x \mid < \mid z \mid$. 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 $S_3$) 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 $S_2$ such that $y$+$p$ is a palindrome. To do this, we take $S_3'$ = $reverse(S_3)$. For every suffix $suf$ of $S_2$, 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$ = $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[i]$. Basically, $temp\_count[i]$ 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[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 $\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.

SAMPLE SOLUTIONS:

Author
Tester
Editorialist

This question is marked "community wiki".

asked 23 Jan '16, 00:19

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156481
accept rate: 4%

edited 10 Mar '16, 13:23

admin's gravatar image

0★admin ♦♦
19.5k348496535

1

@pushkarmishra How are you including palindromes with odd length in the answer?

(25 Jan '16, 05:11) abhishek19953★

Yes indeed

(25 Jan '16, 05:57) pushkarmishra4★

Can't we just merge characters of all three strings and try yo find a palindrome string using characters of merged string. there might be some edge cases where this c program can break.

link

answered 14 Sep '16, 17:23

arunkumar_123's gravatar image

0★arunkumar_123
1
accept rate: 0%

In case 2 : the number of palindromic strings y + p where p is a substring of S3 that start at ith position in S3' has to be $\sum_{r=1}^{k} sum of subs[r+1]$ if k is the z value at position i, instead of sumofsubs[k+1]. Because for every substring p that starts at i in s3' and ends at i+r (r < k) we can take the prefix of corresponding suffix in s2 and add a palindrome that starts at r+1 in s2

NOTE : sumofsubs[r] denotes number of palindromic substrings starting at rth position in s2

link

answered 14 Nov '16, 02:49

durgaprasad726's gravatar image

2★durgaprasad726
11
accept rate: 0%

edited 14 Nov '16, 03:00

I think we can first try all combinations of concatenating strings and the try to find palindrome strings of variable length. We will first try to find a palindrome string of length 2 and then increase the length of palindrome string by one in every iteration.

link

answered 07 Apr '17, 11:46

gmiller's gravatar image

0★gmiller
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,040
×1,919
×1,176
×348
×194
×54
×41
×5

question asked: 23 Jan '16, 00:19

question was seen: 2,534 times

last updated: 22 May, 18:08