Superpalindromlar (Həll təhlili)

Tutaq ki, $s$ — giriş sətri. Alt sətr $s_{i} ... s_{j}$ s_i ... s_j palindromdur, əgər ən azı bir şərt yerinə yetirilirsə:

$i \geq j$ i \ge j, yəni alt sətr boşdur və ya bir simvoldan ibarətdir;
$s_{i} = s_{j}$ s_i = s_j və alt sətr $s_{i + 1} ... s_{j - 1}$ s_{i + 1} ... s_{j - 1} palindromdur;

Funksiya IsPal $(i, j)$ təyin edək, hansı ki, $s_{i} ... s_{j}$ s_i ... s_j alt sətri palindromdursa, $1$ , əks halda $0$ qaytarır.

Algoritmanın işləmə sürətini artırmaq üçün $I s P a l (i, j)$ IsPal(i, j) funksiyasının qiymətlərini iki ölçülü massivin $p a l [i] [j]$ pal[i][j] hüceyrələrində saxlayacağıq.

Sətr superpalindrom adlanır, əgər onu bir və ya bir neçə palindromun konkatenasiyası formasında təqdim etmək olarsa. Məsələn, aşağıdakı sətrlər superpalindromlardır:

Deyək ki,

d p [i] [j] = {1, 0, s alternativ s_{i} \dots s_{j} (i < j) superpalindrom, əks halda .

dp[i][j] = \begin{cases} 1, & \text{s alternativ } s_i \ldots s_j\ (i < j) \text{ superpalindrom,} \\ 0, & \text{əks halda}. \end{cases}

Burada nəzərdə tutulur ki, $i < j$ i < j, yəni alt sətr uzunluğu ən azı iki.

Baza halları qeyd edək:

Eğer $i \geq j$ i \ge j, alt sətr ya boş, ya da bir simvoldan ibarətdir. Şərtə görə bu cür sətrlər palindrom sayılmır. Deməli,

d p [i] [j] = 0 d ə i \geq j

dp[i][j] = 0~də~i ≥ j

Xüsusilə, hər hansı bir mövqe üçün $i$ mövqeyi üçün $d p [i] [i] = 0$ dp[i][i] = 0.

Əgər alt sətr $s_{i} ... s_{j}$ s_i ... s_j palindromdursa və uzunluğu iki və daha çoxdur, o avtomatik olaraq superpalindrom olur (çünki bir palindromdan ibarətdir). Buna görə indekslərin bütün cütləri üçün $(i, j)$ , burada $0 \leq i < j < n$ 0 \le i < j < n, əgər alt sətr $s_{i} ... s_{j}$ s_i ... s_j palindromdursa, dərhal $d p [i] [j] = 1$ dp[i][j] = 1 qura bilərik.

İndi hesabı ümumi halına baxaq. Alt sətr $s_{i} ... s_{j}$ s_i ... s_j tamamilə palindrom deyil. O halda superpalindrom ola bilər əgər onu iki hissəyə bölmək mümkündür ki, hər biri öz növbəsində superpalindrom olsun.

Bunun üçün bütün mümkün bölünmə mövqelərini nəzərdən keçirəcəyik $k (i < k < j - 1)$ k~(i < k < j - 1).

Məhdudiyyət $k < j - 1$ k < j - 1 təmin edir ki, hər iki alt sətr

s_{i} ... s_{k} v ə s_{k + 1} ... s_{j}

s_i ... s_k~və~s_{k+1} ... s_j

uzunluğu ən azı iki, belə ki, potensial olaraq superpalindrom ola bilər.

Əgər bəzi $k$ üçün:

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

alt sətr $s_{i} ... s_{j}$ s_i ... s_j iki superpalindromların konkatenasiyası olaraq təqdim edilir. Deməli, o özü superpalindromdur və biz $d p [i] [j] = 1$ dp[i][j] = 1 quraşdırırıq.

Əgər heç bir uyğun $k$ üçün bu şərtlər yerinə yetirilmirsə, onda $d p [i] [j]$ dp[i][j] sıfır olaraq qalır.

Geriyə $(i, j)$ cütlərinin sayını hesablamaq qalır, harada $i < j$ i < j və $d p [i] [j] = 1$ dp[i][j] = 1. Bu sətir $s$ , alt sətrlər superpalindrom üzərində alt sətrlərin sayıdır.

Misal

Verilmiş misal üçün — sətir " $aba c d c$ ", burada $3$ superpalindrom alt sətr mövcuddur:

Sətir " $aaaba$ " üçün $5$ superpalindrom alt sətr mövcuddur:

Algoritmin həyata keçirilməsi

İşçi massivlər elan edək.

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

Funksiya IsPal $(i, j)$ alt sətrin $s_{i} \dots s_{j}$ s_i \ldots s_j palindrom olub olmadığını yoxlayır. Alt sətr $s_{i} \dots s_{j}$ s_i \ldots s_j palindromdur, əgər $s_{i} = s_{j}$ s_i = s_j və alt sətr $s_{i + 1} \dots s_{j - 1}$ s_{i + 1} \ldots s_{j - 1} də palindromdur.

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

Proqramın əsas hissəsi. Giriş sətirini oxuyuruq. Onun uzunluğunu $n$ hesablayırıq.

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

Massivlər $d p$ və $p a l$ inicializasiya edirik.

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

Bütün alt sətrləri $s_{i} \dots s_{i + l e n}$ s_i \ldots s_{i + len} sətirdən $s$ araşdırırıq uzunluqların artan sırasına görə. Əsas də alt sətrtərin $d p [i] [j]$ dp[i][j] qiyməti daha qısa alt sətrlərin qiymətlərindən asılıdır.

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

Alt sətrin sağ sərhəddi $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;

Əgər alt sətr $s_{i} \dots s_{j}$ s_i \ldots s_j palindromdursa, o, avtomatik olaraq superpalindrom olur.

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

Əgər alt sətr $s_{i} \dots s_{j}$ s_i \ldots s_j palindrom deyilsə, onu iki superpalindromun konkatenasiyası olaraq təqdim etməyə çalışırıq.

Əgər $s_{i} \dots s_{k}$ s_i \ldots s_k və $s_{k + 1} \dots s_{j}$ s_{k+1} \ldots s_j superpalindromlardırsa, onda $s_{i} \dots s_{j}$ s_i \ldots s_j superpalindromdur.

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

C++

Superpalindromların sayını ölçürük. Bu, cüt indekslərin (i, j) sayıdır, hansı ki dp[i][j] = 1.

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

Cavabını çıxarırıq.

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

Algoritmin həyata keçirilməsi – rekursiya

Giriş sətiri $s$ elan edək və işçi massivlər.

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

Funksiya IsPal $(i, j)$ alt sətrin $s_{i} \dots s_{j}$ s_i \ldots s_j palindrom olub olmadığını yoxlayır. Alt sətr $s_{i} \dots s_{j}$ s_i \ldots s_j palindromdır əgər $s_{i} = s_{j}$ s_i = s_j və alt sətr $s_{i + 1} \dots s_{j - 1}$ s_{i + 1} \ldots s_{j - 1} də palindromdır.

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

Funksiya f $(i, j)$ $s_{i} \dots s_{j}$ s_i \ldots s_j superpalindromdursa, $1$ qaytarır.

int f(int i, int j)
{

Superpalindrom daha çox simvol ehtiva etməlidir.

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

Əgər f $(i, j)$ artıq əvvəllər hesablanıbsa, onun qiymətini qaytarırıq.

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

Əgər alt sətr $s_{i} \dots s_{j} (i < j)$ s_i \ldots s_j~(i < j) palindromdursa, o həm də superpalindrom olur.

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

Əgər alt sətr $s_{i} \dots s_{k} (i < k)$ s_i \ldots s_k~(i < k) palindromdursa, alt sətr $s_{k + 1} \dots s_{j} (k + 1 < j)$ s_{k+1} \ldots s_j~(k + 1 < j) superpalindromdursa, alt sətr $s_{i} \dots s_{j}$ s_i \ldots s_j superpalindromdur.

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

Əgər yuxarıda təsvir edilən heç bir şərtlər yerinə yetirilmirsə, alt sətr $s_{i} \dots s_{j}$ s_i \ldots s_j superpalindrom deyil.

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

Proqramın əsas hissəsi. Giriş sətirini $s$ oxuyurq və onun uzunluğunu $n$ hesablayırıq.

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

Massivlər $d p$ və $p a l$ inicializasiya edirik.

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

Superpalindromların sayını $r es$ dəyişənində hesablayırıq.

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

Cavabını çıxarırıq.

cout << res << endl;

Java həyata keçirilməsi

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