Суперпаліндроми (Розбір)

Нехай $s$ — вхідний рядок. Підрядок $s_{i} ... s_{j}$ s_i ... s_j є паліндромом, якщо виконується хоча б одна з наступних умов:

$i \geq j$ i \ge j, тобто підрядок порожній або складається з одного символу;
$s_{i} = s_{j}$ s_i = s_j і підрядок $s_{i + 1} ... s_{j - 1}$ s_{i + 1} ... s_{j - 1} є паліндромом;

Визначимо функцію IsPal $(i, j)$ , яка повертає $1$ , якщо підрядок $s_{i} ... s_{j}$ s_i ... s_j є паліндромом, і $0$ в іншому випадку.

Для прискорення роботи алгоритму значення функції $I s P a l (i, j)$ IsPal(i, j) будемо зберігати в комірках двовимірного масиву $p a l [i] [j]$ pal[i][j].

Рядок називається суперпаліндромом, якщо її можна представити у вигляді конкатенації одного або кількох паліндромів. Наприклад, наступні рядки є суперпаліндромами:

Нехай

d p [i] [j] = {1, 0, якщо підрядок s_{i} \dots s_{j} (i < j) є суперпаліндромом, інакше .

dp[i][j] = \begin{cases} 1, & \text{якщо підрядок } s_i \ldots s_j\ (i < j) \text{ є суперпаліндромом}, \\ 0, & \text{інакше}. \end{cases}

Тут передбачається, що $i < j$ i < j, тобто довжина підрядка не менше двох.

Зазначимо базові випадки:

Якщо $i \geq j$ i \ge j, то підрядок або порожній, або складається з одного символу. Такі рядки не вважаються паліндромами за умовою. Отже,

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

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

Зокрема, для будь-якої позиції $i$ маємо $d p [i] [i] = 0$ dp[i][i] = 0.

Якщо підрядок $s_{i} ... s_{j}$ s_i ... s_j є паліндромом і її довжина не менше двох, то вона автоматично є суперпаліндромом (оскільки складається з одного паліндрома). Тому для всіх пар індексів $(i, j)$ , де $0 \leq i < j < n$ 0 \le i < j < n, якщо підрядок $s_{i} ... s_{j}$ s_i ... s_j паліндром, ми можемо відразу встановити $d p [i] [j] = 1$ dp[i][j] = 1.

Тепер розглянемо загальний випадок. Нехай підрядок $s_{i} ... s_{j}$ s_i ... s_j не є паліндромом цілком. Тоді вона все ще може бути суперпаліндромом, якщо її можна розбити на дві частини, кожна з яких є суперпаліндромом.

Для цього переберемо всі можливі позиції розбиття $k (i < k < j - 1)$ k~(i < k < j - 1).

Обмеження $k < j - 1$ k < j - 1 гарантує, що обидва підрядки

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

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

мають довжину не менше двох, а значить, потенційно можуть бути суперпаліндромами.

Якщо для деякого $k$ виконується:

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

то підрядок $s_{i} ... s_{j}$ s_i ... s_j представлений у вигляді конкатенації двох суперпаліндромів. Отже, вона сама є суперпаліндромом, і ми встановлюємо $d p [i] [j] = 1$ dp[i][j] = 1.

Якщо ж ні для одного допустимого $k$ це умова не виконується, то $d p [i] [j]$ dp[i][j] залишається рівним нулю.

Залишається підрахувати кількість пар $(i, j)$ , для яких $i < j$ i < j і $d p [i] [j] = 1$ dp[i][j] = 1. Це і є число підрядків рядка $s$ , які є суперпаліндромами.

Приклад

Для заданого прикладу — рядка " $aba c d c$ ", існує $3$ підрядки, які є суперпаліндромами:

Для рядка " $aaaba$ " існує $5$ підрядків, які є суперпаліндромами:

Реалізація алгоритму

Оголосимо робочі масиви.

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

Функція IsPal $(i, j)$ перевіряє, чи підрядок $s_{i} \dots s_{j}$ s_i \ldots s_j є паліндромом. Підрядок $s_{i} \dots s_{j}$ s_i \ldots s_j є паліндромом, якщо $s_{i} = s_{j}$ s_i = s_j і підрядок $s_{i + 1} \dots s_{j - 1}$ s_{i + 1} \ldots s_{j - 1} також є паліндромом. Значення функції IsPal $(i, j)$ зберігаються в комірках двовимірного масиву $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);
}

Основна частина програми. Читаємо вхідний рядок. Обчислюємо її довжину $n$ .

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

Ініціалізуємо масиви $d p$ і $p a l$ .

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

Перебираємо всі підрядки $s_{i} \dots s_{i + l e n}$ s_i \ldots s_{i + len} рядка $s$ в порядку зростання їх довжини $l e n$ . Це важливо, оскільки значення $d p [i] [j]$ dp[i][j] залежить від значень для коротших підрядків.

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

Права межа підрядка $s_{i} \dots s_{i + l e n}$ s_i \ldots s_{i + len} дорівнює $j = i + l e n$ j = i + len.

  j = i + len;

Якщо підрядок $s_{i} \dots s_{j}$ s_i \ldots s_j є паліндромом, то вона автоматично є і суперпаліндромом.

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

Якщо підрядок $s_{i} \dots s_{j}$ s_i \ldots s_j не є паліндромом, ми намагаємося представити її у вигляді конкатенації двох суперпаліндромів.

Якщо $s_{i} \dots s_{k}$ s_i \ldots s_k і $s_{k + 1} \dots s_{j}$ s_{k+1} \ldots s_j суперпаліндроми, то $s_{i} \dots s_{j}$ s_i \ldots s_j є суперпаліндромом.

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

C++

Підраховуємо кількість суперпаліндромів. Воно дорівнює кількості пар індексів (i, j), для яких dp[i][j] = 1.

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

Виводимо відповідь.

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

Реалізація алгоритму – рекурсія

Оголосимо вхідний рядок $s$ і робочі масиви.

#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);
}

Функція f $(i, j)$ повертає $1$ , якщо $s_{i} \dots s_{j}$ s_i \ldots s_j є суперпаліндромом.

int f(int i, int j)
{

Суперпаліндром повинен містити більше одного символу.

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

Якщо значення f $(i, j)$ вже було обчислено раніше, повертаємо його значення.

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

Якщо підрядок $s_{i} \dots s_{j} (i < j)$ s_i \ldots s_j~(i < j) є паліндромом, то вона також є і суперпаліндромом.

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

Якщо підрядок $s_{i} \dots s_{k} (i < k)$ s_i \ldots s_k~(i < k) є паліндромом, а підрядок $s_{k + 1} \dots s_{j} (k + 1 < j)$ s_{k+1} \ldots s_j~(k + 1 < j) є суперпаліндромом, то підрядок $s_{i} \dots s_{j}$ s_i \ldots s_j є суперпаліндромом.

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

Якщо жодна із описаних вище умов не виконується, то підрядок $s_{i} \dots s_{j}$ s_i \ldots s_j не є суперпаліндромом.

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

Основна частина програми. Читаємо вхідний рядок $s$ і обчислюємо її довжину $n$ .

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

Ініціалізуємо масиви $d p$ і $p a l$ .

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

У змінній $r es$ підраховуємо кількість суперпаліндромів.

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

Виводимо відповідь.

cout << res << endl;

Java реалізація

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