470. Суперпалиндромы

 

Назовём палиндромом строку длины более одного символа, которая читается одинаково слева направо и справа налево.

Суперпалиндромом назовем строку, которую можно представить в виде конкатенации одного или нескольких палиндромов.

Дана строка s. Найдите количество подстрок строки s, являющихся суперпалиндромами.

 

Вход. Одна строка s (1 ≤ s ≤ 1000), состоящая из строчных латинских букв.

 

Выход. Выведите одно число – количество подстрок строки s, которые являются суперпалиндромами.

 

Пример входа

Пример выхода

abacdc

3

 

 

РЕШЕНИЕ

динамическое программирование - палиндромы

 

Анализ алгоритма

Пусть s – входная строка. Подстрока si … sj является палиндромом, если выполняется хотя бы одно из следующих условий:

·        i ≥ j, то есть подстрока пустая или состоит из одного символа;

·        si = sj и подстрока si+1…sj-1 является палиндромом;

 

Определим функцию IsPal(i, j), которая возвращает 1, если подстрока si…sj является палиндромом, и 0 в противном случае.

Для ускорения работы алгоритма значения функции IsPal(i, j) будем сохранять в ячейках двумерного массива pal[i][j].

 

Строка называется суперпалиндромом, если её можно представить в виде конкатенации одного или нескольких палиндромов. Например, следующие строки являются суперпалиндромами:

 

Пусть

 

Здесь предполагается, что i < j, то есть длина подстроки не меньше двух.

 

Отметим базовые случаи:

·        Если i ≥ j, то подстрока либо пуста, либо состоит из одного символа. Такие строки не считаются палиндромами по условию. Следовательно,

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

·        В частности, для любой позиции i имеем dp[i][i] = 0.

 

Если подстрока si…sj является палиндромом и её длина не меньше двух, то она автоматически является суперпалиндромом (так как состоит из одного палиндрома). Поэтому для всех пар индексов (i, j), где 0 ≤ i < j < n, если подстрока si…sj палиндром, мы можем сразу установить dp[i][j] = 1.

 

Теперь рассмотрим общий случай. Пусть подстрока si…sj не является палиндромом целиком. Тогда она всё ещё может быть суперпалиндромом, если её можно разбить на две части, каждая из которых является суперпалиндромом.

Для этого переберём все возможные позиции разбиения k (i < k < j – 1).

Ограничение k < j – 1 гарантирует, что обе подстроки

si…sk и sk+1…sj

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

Если для некоторого k выполнено:

·        dp[i][k] = 1,

·        dp[k + 1][j] = 1,

то подстрока si…sj представляется в виде конкатенации двух суперпалиндромов. Следовательно, она сама является суперпалиндромом, и мы устанавливаем dp[i][j] = 1.

Если же ни для одного допустимого k это условие не выполняется, то dp[i][j] остаётся равным нулю.

 

Остается подсчитать количество пар (i, j), для которых i < j и dp[i][j] = 1. Это и есть число подстрок строки s, являющихся суперпалиндромами

 

Пример

Для заданного примера – строки “abacdc”, существует 3 подстроки, являющиеся суперпалиндромами:

 

Для строки “aaaba” существует 5 подстрок, которые являются суперпалиндромами:

 

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

Объявим рабочие массивы.

 

#define MAX 1010

char s[MAX];

int dp[MAX][MAX];

int pal[MAX][MAX];

 

Функция IsPal(i, j) проверяет, является ли подстрока si…sj палиндромом. Подстрока si … sj является палиндромом, если si = sj и подстрока si+1…sj-1 также является палиндромом. Значения функции IsPal(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();

 

Инициализируем массивы dp и pal.

 

memset(dp,0,sizeof(dp));

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

 

Перебираем все подстроки si … si + len строки s в порядке возрастания их длины len. Это важно, поскольку значение dp[i][j] зависит от значений для более коротких подстрок.

 

for (len = 1; len < n; len++)

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

{

 

Правая граница подстроки si … si + len равна j = i + len.

 

  j = i + len;

 

Если подстрока si…sj является палиндромом, то она автоматически является и суперпалиндромом.

 

  if (IsPal(i,j))

  {

    dp[i][j] = 1;

    continue;

  }

 

Если подстрока si…sj не является палиндромом, мы пытаемся представить её в виде конкатенации двух суперпалиндромов.

Если si…sk и sk+1…sj суперпалиндромы, то si…sj является суперпалиндромом.

 

  for(k = i + 1; k < j - 1; k++)

    if(dp[i][k] && dp[k + 1][j])

    {

      dp[i][j] = 1;

      break;

    }

}

 

Подсчитываем количество суперпалиндромов. Оно равно количеству пар индексов (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];

 

Функция IsPal(i, j) проверяет, является ли подстрока si…sj палиндромом. Подстрока si … sj является палиндромом, если si = sj и подстрока si+1…sj-1 также является палиндромом. Значения функции IsPal(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);

}

 

Функция f(i, j) возвращает 1, если si…sj является суперпалиндромом.

 

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];

 

Если подстрока si…sj (i < j) является палиндромом, то она также является и суперпалиндромом.

 

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

 

Если подстрока si…sk (i < k) является палиндромом, а подстрока sk+1…sj (k + 1 < j) является суперпалиндромом, то подстрока si…sj является суперпалиндромом.

 

  for (int k = i + 1; k < j - 1; k++)

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

 

Если ни одно из описанных выше условий не выполняется, то подстрока si…sj не является суперпалиндромом.

 

  return dp[i][j] = 0;

}

 

Основная часть программы. Читаем входную строку s и вычисляем ее длину n.

 

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

 

Инициализируем массивы dp и pal.

 

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

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

 

В переменой res подсчитываем количество суперпалиндромов.

 

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

  }

}