Super palindromes (Editorial)

Let $s$ be the input string. A substring $s_{i} ... s_{j}$ s_i ... s_j is a palindrome if at least one of the following conditions is satisfied:

$i \geq j$ i \ge j, that is, the substring is empty or consists of a single character;
$s_{i} = s_{j}$ s_i = s_j and the substring $s_{i + 1} ... s_{j - 1}$ s_{i + 1} ... s_{j - 1} is a palindrome;

Let's define the function IsPal $(i, j)$ , that returns $1$ if the substring $s_{i} ... s_{j}$ s_i ... s_j is a palindrome, and $0$ otherwise.

To speed up the algorithm, the values of $I s P a l (i, j)$ IsPal(i, j) are stored in the cells of a two-dimensional array $p a l [i] [j]$ pal[i][j].

A string is called a superpalindrome if it can be represented as a concatenation of one or more palindromes. For example, the following strings are superpalindromes:

Let

d p [i] [j] = {1, 0, if the substring s_{i} \dots s_{j} (i < j) is a superpalindrome, otherwise .

dp[i][j] = \begin{cases} 1, & \text{if the substring } s_i \ldots s_j\ (i < j) \text{ is a superpalindrome}, \\ 0, & \text{ otherwise}. \end{cases}

Here it is assumed that $i < j$ i < j, that is, the length of the substring is at least two.

Let us note the base cases:

If $i \geq j$ i \ge j, then the substring is either empty or consists of a single character. Such strings are not considered palindromes by definition. Therefore,

d p [i] [j] = 0 при i \geq j

dp[i][j] = 0~при~i ≥ j

In particular, for any position $i$ , we have $d p [i] [i] = 0$ dp[i][i] = 0.

If the substring $s_{i} ... s_{j}$ s_i ... s_j is a palindrome and its length is at least two, then it is automatically a superpalindrome (since it consists of a single palindrome). Therefore, for all pairs of indices $(i, j)$ where $0 \leq i < j < n$ 0 \le i < j < n, if the substring $s_{i} ... s_{j}$ s_i ... s_j is a palindrome, we can immediately set $d p [i] [j] = 1$ dp[i][j] = 1.

Now consider the general case. Let the substring $s_{i} ... s_{j}$ s_i ... s_j not be a palindrome as a whole. It can still be a superpalindrome if it can be split into two parts, each of which is a superpalindrome.

To do this, iterate over all possible split positions $k$ such that $i < k < j - 1$ i < k < j - 1.

The restriction $k < j - 1$ k < j - 1 ensures that both substrings

s_{i} ... s_{k} и s_{k + 1} ... s_{j}

s_i ... s_k~и~s_{k+1} ... s_j

have length at least two, and therefore can potentially be superpalindromes.

If, for some $k$ , the following conditions are satisfied:

$d p [i] [k] = 1$ dp[i][k] = 1,
$d p [k + 1] [j] = 1$ dp[k + 1][j] = 1,

then the substring $s_{i} ... s_{j}$ s_i ... s_j can be represented as a concatenation of two superpalindromes. Therefore, it is itself a superpalindrome, and we set $d p [i] [j] = 1$ dp[i][j] = 1.

If this condition is not satisfied for any valid $k$ , then $d p [i] [j]$ dp[i][j] remains $0$ .

Finally, count the number of pairs $(i, j)$ for which $i < j$ i < j and $d p [i] [j] = 1$ dp[i][j] = 1. This count is exactly the number of substrings of the string $s$ that are superpalindromes.

Example

For the given example — the string " $aba c d c$ " — there are $3$ substrings that are superpalindromes:

For the string " $aaaba$ ", there are $5$ substrings that are superpalindromes:

Algorithm implementation

Declare the arrays.

#define MAX 1010
char s[MAX];
int dp[MAX][MAX];
int pal[MAX][MAX];

The function IsPal $(i, j)$ checks whether the substring $s_{i} \dots s_{j}$ s_i \ldots s_j is a palindrome. The substring $s_{i} \dots s_{j}$ s_i \ldots s_j is a palindrome if $s_{i} = s_{j}$ s_i = s_j and the substring $s_{i + 1} \dots s_{j - 1}$ s_{i + 1} \ldots s_{j - 1} is also a palindrome. The values of the function IsPal $(i, j)$ are stored in the cells of the two-dimensional array $p a l [i] [j]$ pal[i][j].

int IsPal(int i, int j)
{
  if (i >= j) return pal[i][j] = 1;
  if (pal[i][j] != -1) return pal[i][j];
  return pal[i][j] = (s[i] == s[j]) && IsPal(i + 1,j - 1);
}

The main part of the program. Read the input string $s$ and compute its length $n$ .

cin >> s; n = s.size();

Initialize the arrays $d p$ and $p a l$ .

memset(dp,0,sizeof(dp));
memset(pal,-1,sizeof(pal));

Iterate over all substrings $s_{i} \dots s_{i + l e n}$ s_i \ldots s_{i + len} of the string $s$ in increasing order of their length $l e n$ . This is important because the value of $d p [i] [j]$ dp[i][j] depends on the values for shorter substrings.

for (len = 1; len < n; len++)
for (i = 0; i + len < n; i++)
{

The right boundary of the substring $s_{i} \dots s_{i + l e n}$ s_i \ldots s_{i + len} is $j = i + l e n$ j = i + len.

  j = i + len;

If the substring $s_{i} \dots s_{j}$ s_i \ldots s_j is a palindrome, then it is automatically also a superpalindrome.

  if (IsPal(i,j))
  {
    dp[i][j] = 1;
    continue;
  }

If the substring $s_{i} \dots s_{j}$ s_i \ldots s_j is not a palindrome, we try to represent it as a concatenation of two superpalindromes.

If $s_{i} \dots s_{k}$ s_i \ldots s_k and $s_{k + 1} \dots s_{j}$ s_{k+1} \ldots s_j are superpalindromes, then $s_{i} \dots s_{j}$ s_i \ldots s_j is a superpalindrome as well.

  for (k = i + 1; k < j - 1; k++)
    if (dp[i][k] && dp[k + 1][j])
    {
      dp[i][j] = 1;
      break;
    }
}

C++

Count the number of superpalindromes. It is equal to the number of index pairs (i, j) for which dp[i][j] = 1.

res = 0;
for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++)
  res += dp[i][j];

Print the answer.

printf("%d\n",res);

Algorithm implementation – recursion

Declare the input string $s$ and arrays.

#define MAX 1010
string s;
int dp[MAX][MAX], pal[MAX][MAX];

int IsPal(int i, int j)
{
  if (i >= j) return pal[i][j] = 1;
  if (pal[i][j] != -1) return pal[i][j];
  return pal[i][j] = (s[i] == s[j]) && IsPal(i+1,j-1);
}

The function f $(i, j)$ returns $1$ if the substring $s_{i} \dots s_{j}$ s_i \ldots s_j is a superpalindrome.

int f(int i, int j)
{

A superpalindrome must contain more than one character.

  if (i == j) return dp[i][j] = 0;

If the value of f $(i, j)$ is already computed, return this value.

  if (dp[i][j] != -1) return dp[i][j];

If the substring $s_{i} \dots s_{j} (i < j)$ s_i \ldots s_j~(i < j) is a palindrome, then it is also a superpalindrome.

  if (IsPal(i,j)) return dp[i][j] = 1;

If the substring $s_{i} \dots s_{k} (i < k)$ s_i \ldots s_k~(i < k) is a palindrome and the substring $s_{k + 1} \dots s_{j} (k + 1 < j)$ s_{k+1} \ldots s_j~(k + 1 < j) is a superpalindrome, then the substring $s_{i} \dots s_{j}$ s_i \ldots s_j is a superpalindrome.

  for (int k = i + 1; k < j - 1; k++)
    if (IsPal(i,k) && f(k + 1,j)) return dp[i][j] = 1;

If none of the conditions described above is satisfied, then the substring $s_{i} \dots s_{j}$ s_i \ldots s_j is not a superpalindrome.

  return dp[i][j] = 0;
}

The main part of the program. Read the input string $s$ and compute its length $n$ .

cin >> s; n = s.size();

Initialize the arrays $d p$ and $p a l$ .

memset(dp,-1,sizeof(dp));
memset(pal,-1,sizeof(pal));

In the variable $r es$ count the number of superpalindromes.

res = 0;
for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++)
  res += f(i,j);

Print the answer.

cout << res << endl;

Java implementation

import java.util.*;

public class Main 
{
  static String s;
  static int dp[][], pal[][];

  static int IsPal(int i, int j)
  {
    if (i >= j) return pal[i][j] = 1;
    if (pal[i][j] != -1) return pal[i][j];
    if (s.charAt(i) == s.charAt(j) && IsPal(i+1,j-1) == 1) pal[i][j] = 1;
    else pal[i][j] = 0;
    return pal[i][j];
  }
 
  static int f(int i, int j)
  {
    if (i == j) return dp[i][j] = 0;
    if (dp[i][j] != -1) return dp[i][j];
    if (IsPal(i,j) == 1) return dp[i][j] = 1;

    for(int k = i + 1; k < j - 1; k++)
      if(IsPal(i,k) == 1 && f(k + 1,j) == 1) return dp[i][j] = 1;

    return dp[i][j] = 0;
  }
	
  public static void main(String[] args) 
  {
    Scanner con = new Scanner(System.in);
    s = con.nextLine();
    int n = s.length();
    dp = new int[n][n];
    pal = new int[n][n];
    for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
    {
      dp[i][j] = -1;
      pal[i][j] = -1;
    }

    int res = 0;
    for(int i = 0; i < n; i++)
    for(int j = i+1; j < n; j++)
      res += f(i,j);
    
    System.out.println(res);
    con.close();
  }
}

Java