Рубрики

Подсчитать все подстроки палиндрома в строке | Комплект 1

По заданной строке задача состоит в том, чтобы подсчитать все подстроки палиндрома в данной строке. Длина подстроки палиндрома больше или равна 2.
Примеры:

Input : str = "abaab"
Output: 3
Explanation : 
All palindrome substring are :
 "aba" , "aa" , "baab" 

Input : str = "abbaeae"
Output: 4
Explanation : 
All palindrome substring are : 
"bb" , "abba" ,"aea","eae"

Мы обсудили подобную проблему ниже.
Найти все различные палиндромные подстроки данной строки

Вышеуказанная проблема может быть рекурсивно определена.

Initial Values : i = 0, j = n-1;
Given string 'str'

CountPS(i, j)
   
   // If length of string is 2 then we 
   // check both character are same or not 
   If (j == i+1)
      return str[i] == str[j]

   Else If str[i..j] is PALINDROME 
      // increment count by 1 and check for 
      // rest palindromic substring (i, j-1), (i+1, j)
      // remove common palindrome substring (i+1, j-1)
      return  countPS(i+1, j) + countPS(i, j-1) + 1 -
                                   countPS(i+1, j-1);

    Else // if NOT PALINDROME 
       // We check for rest palindromic substrings (i, j-1)
       // and (i+1, j)
       // remove common palindrome substring (i+1 , j-1)
       return  countPS(i+1, j) + countPS(i, j-1) - 
                             countPS(i+1 , j-1);

Если мы рисуем рекурсивное дерево выше рекурсивного решения, мы можем наблюдать перекрывающиеся подзадачи . Поскольку проблема имеет перекрывающиеся подзадачи, мы можем эффективно решить ее с помощью динамического программирования. Ниже представлено решение на основе динамического программирования.

C / C ++

// C ++ программа для поиска палиндромных подстрок строки
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает общее количество подстрок палиндрома
// длина больше 2

int CountPS(char str[], int n)

{

    // создаем пустую двумерную матрицу, которая считает весь палиндром

    // подстрока. dp [i] [j] хранит количество палиндромных

    // подстроки в st [i..j]

    int dp[n][n];

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

  

    // P [i] [j] = true, если подстрока str [i..j] является палиндромом,

    // иначе ложь

    bool P[n][n];

    memset(P, false , sizeof(P));

  

    // палиндром одинарной длины

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

        P[i][i] = true;

  

    // палиндром длины 2

    for (int i=0; i<n-1; i++)

    {

        if (str[i] == str[i+1])

        {

            P[i][i+1] = true;

            dp[i][i+1] = 1 ;

        }

    }

  

    // Палиндромы длиной более 2. Этот цикл похож

    // к матричному умножению. Начнем с разрыва

    // длина 2 и заполнить таблицу DP таким образом, чтобы промежуток между

    // начальный и конечный индексы увеличиваются один за другим

    // внешний цикл

    for (int gap=2 ; gap<n; gap++)

    {

        // Выбрать начальную точку для текущего разрыва

        for (int i=0; i<n-gap; i++)

        {

            // Установить конечную точку

            int j = gap + i;

  

            // Если текущей строкой является палиндром

            if (str[i] == str[j] && P[i+1][j-1] )

                P[i][j] = true;

  

            // Добавить текущую подстроку палиндрома (+ 1)

            // и остальная подстрока палиндрома (dp [i] [j-1] + dp [i + 1] [j])

            // удаляем общие палиндромные подстроки (- dp [i + 1] [j-1])

            if (P[i][j] == true)

                dp[i][j] = dp[i][j-1] + dp[i+1][j] + 1 - dp[i+1][j-1];

            else

                dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1];

        }

    }

  

    // возвращаем общее количество палиндромных подстрок

    return dp[0][n-1];

}

  
// Драйвер программы

int main()

{

    char str[] = "abaab";

    int n = strlen(str);

    cout << CountPS(str, n) << endl;

    return 0;

}

Джава

// Java-программа для поиска палиндромных подстрок строки

  

public class GFG 

{

    // Возвращает общее количество подстрок палиндрома

    // длина больше 2

    static int CountPS(char str[], int n)

    {

        // создаем пустую двумерную матрицу, которая считает весь палиндром

        // подстрока. dp [i] [j] хранит количество палиндромных

        // подстроки в st [i..j]

        int dp[][] = new int[n][n];

       

        // P [i] [j] = true, если подстрока str [i..j] является палиндромом,

        // иначе ложь

        boolean P[][] = new boolean[n][n];

       

        // палиндром одинарной длины

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

            P[i][i] = true;

       

        // палиндром длины 2

        for (int i=0; i<n-1; i++)

        {

            if (str[i] == str[i+1])

            {

                P[i][i+1] = true;

                dp[i][i+1] = 1 ;

            }

        }

       

        // Палиндромы длиной более 2. Этот цикл похож

        // к матричному умножению. Начнем с разрыва

        // длина 2 и заполнить таблицу DP таким образом, чтобы промежуток между

        // начальный и конечный индексы увеличиваются один за другим

        // внешний цикл

        for (int gap=2 ; gap<n; gap++)

        {

            // Выбрать начальную точку для текущего разрыва

            for (int i=0; i<n-gap; i++)

            {

                // Установить конечную точку

                int j = gap + i;

       

                // Если текущей строкой является палиндром

                if (str[i] == str[j] && P[i+1][j-1] )

                    P[i][j] = true;

       

                // Добавить текущую подстроку палиндрома (+ 1)

                // и остальная подстрока палиндрома (dp [i] [j-1] + dp [i + 1] [j])

                // удаляем общие палиндромные подстроки (- dp [i + 1] [j-1])

                if (P[i][j] == true)

                    dp[i][j] = dp[i][j-1] + dp[i+1][j] + 1 - dp[i+1][j-1];

                else

                    dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1];

            }

        }

       

        // возвращаем общее количество палиндромных подстрок

        return dp[0][n-1];

    }

      

    // Метод драйвера

    public static void main(String[] args)

    {

        String str = "abaab";

        System.out.println(CountPS(str.toCharArray(), str.length()));

    }

}

Python 3

# Python 3 программа для поиска палиндромов
# подстроки строки

  
# Возвращает общее количество палиндрома
# подстрока длины больше чем
# равно 2

def CountPS(str, n):

  

    # создать пустую двумерную матрицу, которая считает

    # вся палиндромная подстрока. дп [I] [J]

    Количество магазинов палиндромных

    # подстрок в st [i..j]

    dp = [[0 for x in range(n)]

             for y in range(n)]

  

    # P [i] [j] = true, если подстрока str [i..j]

    # - палиндром, иначе ложь

    P = [[False for x in range(n)]

                for y in range(n)]

  

    # палиндром одинарной длины

    for i in range(n):

        P[i][i] = True

  

    # палиндром длины 2

    for i in range(n - 1):

        if (str[i] == str[i + 1]):

            P[i][i + 1] = True

            dp[i][i + 1] = 1

  

    # Палиндромы длиной более 2. Это

    Цикл # аналогичен умножению матрицы.

    # Начинаем с пробела длины 2 и заполняем DP

    # таблица таким образом, чтобы разрыв между началом и

    # конечные индексы увеличиваются один за другим

    # внешний цикл.

    for gap in range(2, n):

          

        # Выберите начальную точку для текущего разрыва

        for i in range(n - gap):

              

            # Установить конечную точку

            j = gap + i;

  

            # Если текущая строка - палиндром

            if (str[i] == str[j] and P[i + 1][j - 1]):

                P[i][j] = True

  

            # Добавить текущую подстроку палиндрома (+ 1)

            # и остальная палиндромная подстрока (dp [i] [j-1] +

            # dp [i + 1] [j]) удалить общий палиндром

            # подстроки (- dp [i + 1] [j-1])

            if (P[i][j] == True):

                dp[i][j] = (dp[i][j - 1] + 

                            dp[i + 1][j] + 1 - dp[i + 1][j - 1])

            else:

                dp[i][j] = (dp[i][j - 1] + 

                            dp[i + 1][j] - dp[i + 1][j - 1])

  

    # вернуть общее количество палиндромных подстрок

    return dp[0][n - 1]

  
Код водителя

if __name__ == "__main__":

      

    str = "abaab"

    n = len(str)

    print(CountPS(str, n))

  
# Этот код предоставлен ita_c

C #

// C # программа для поиска палиндромов
// подстроки строки

using System;

  

class GFG

{
// Возвращает общее количество
// палиндромная подстрока
// длина больше 2

public static int CountPS(char[] str, 

                          int n)

{

    // создаем пустую двумерную матрицу, которая считает

    // вся палиндромная подстрока. дп [I] [J]

    // хранит количество палиндромных

    // подстроки в st [i..j]

  

    int[][] dp = RectangularArrays.ReturnRectangularIntArray(n, n);

  

    // P [i] [j] = true, если подстрока str [i..j]

    // это палиндром, иначе ложь

  

    bool[][] P = RectangularArrays.ReturnRectangularBoolArray(n, n);

  

    // палиндром одинарной длины

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

    {

        P[i][i] = true;

    }

  

    // палиндром длины 2

    for (int i = 0; i < n - 1; i++)

    {

        if (str[i] == str[i + 1])

        {

            P[i][i + 1] = true;

            dp[i][i + 1] = 1;

        }

    }

  

    // Палиндромы длиной более 2.

    // Этот цикл похож на Matrix Chain

    // Умножение. Начнем с разрыва

    // длины 2 и заполнить таблицу DP в

    // преодолеть этот разрыв между началом и

    // окончание индексов увеличивается один за другим

    // по внешнему циклу.

    for (int gap = 2 ; gap < n; gap++)

    {

        // Выбрать начальную точку для текущего разрыва

        for (int i = 0; i < n - gap; i++)

        {

            // Установить конечную точку

            int j = gap + i;

  

            // Если текущей строкой является палиндром

            if (str[i] == str[j] && P[i + 1][j - 1])

            {

                P[i][j] = true;

            }

  

            // Добавить текущую палиндромную подстроку

            // (+ 1) и остальная палиндромная подстрока

            // (dp [i] [j-1] + dp [i + 1] [j]) удалить общий

            // палиндромные подстроки (- dp [i + 1] [j-1])

            if (P[i][j] == true)

            {

                dp[i][j] = dp[i][j - 1] +

                           dp[i + 1][j] + 1 - dp[i + 1][j - 1];

            }

            else

            {

                dp[i][j] = dp[i][j - 1] + 

                           dp[i + 1][j] - dp[i + 1][j - 1];

            }

        }

    }

  

    // возвращаем общее количество палиндромных подстрок

    return dp[0][n - 1];

}

  

public static class RectangularArrays

{

public static int[][] ReturnRectangularIntArray(int size1,

                                                int size2)

{

    int[][] newArray = new int[size1][];

    for (int array1 = 0; 

             array1 < size1; array1++)

    {

        newArray[array1] = new int[size2];

    }

  

    return newArray;

}

  

public static bool[][] ReturnRectangularBoolArray(int size1,    

                                                  int size2)

{

    bool[][] newArray = new bool[size1][];

    for (int array1 = 0; array1 < size1; array1++)

    {

        newArray[array1] = new bool[size2];

    }

  

    return newArray;

}
}

  
// Код драйвера

public static void Main(string[] args)

{

    string str = "abaab";

    Console.WriteLine(CountPS(str.ToCharArray(), str.Length));

}
}

  
// Этот код предоставлен Shrikant13

PHP

<?php
// PHP программа для поиска палиндромных подстрок
// строки

  
// Возвращает общее количество палиндрома
// подстрока длиной больше 2

function CountPS($str, $n

    // создаем пустую двумерную матрицу, которая считает

    // вся палиндромная подстрока. дп [I] [J]

    // хранит количество палиндромных

    // подстроки в st [i..j]

    $dp = array(array());

      

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

        for($j = 0; $j < $n; $j++)

            $dp[$i][$j] = 0;

  

    // P [i] [j] = true, если подстрока str [i..j]

    // это палиндром, иначе ложь

    $P = array(array());

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

            for($j = 0; $j < $n; $j++)

                $P[$i][$j] = false;

  

    // палиндром одинарной длины

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

        $P[$i][$i] = true; 

  

    // палиндром длины 2

    for ($i = 0; $i < $n - 1; $i++) 

    

        if ($str[$i] == $str[$i + 1]) 

        

            $P[$i][$i + 1] = true; 

            $dp[$i][$i + 1] = 1; 

        

    

  

    // Палиндромы длиной более 2. Это

    // цикл похож на умножение матрицы.

    // Начинаем с пробела длины 2 и заполняем DP

    // таблица таким образом, чтобы разрыв между началом и

    // окончание индексов увеличивается один за другим

    // внешний цикл

    for ($gap = 2; $gap < $n; $gap++) 

    

        // Выбрать начальную точку для текущего разрыва

        for ($i = 0; $i < $n - $gap; $i++) 

        

            // Установить конечную точку

            $j = $gap + $i

  

            // Если текущей строкой является палиндром

            if ($str[$i] == $str[$j] && $P[$i + 1][$j - 1]) 

                $P[$i][$j] = true; 

  

            // Добавить текущую подстроку палиндрома (+ 1)

            // и остальная подстрока палиндрома (dp [i] [j-1] +

            // dp [i + 1] [j]) удаляем общий палиндром

            // подстроки (- dp [i + 1] [j-1])

            if ($P[$i][$j] == true) 

                $dp[$i][$j] = $dp[$i][$j - 1] + 

                              $dp[$i + 1][$j] + 1 - 

                              $dp[$i + 1][$j - 1]; 

            else

                $dp[$i][$j] = $dp[$i][$j - 1] + 

                              $dp[$i + 1][$j] - 

                              $dp[$i + 1][$j - 1]; 

        

    

  

    // возвращаем общее количество палиндромных подстрок

    return $dp[0][$n - 1]; 

  
// Код драйвера

$str = "abaab"

$n = strlen($str); 

echo CountPS($str, $n);

  
// Этот код предоставлен Ryuga
?>


Выход:

3

Временная сложность: O (n 2 )
Вспомогательное пространство: O (n 2 )

Подсчитать все подстроки палиндрома в строке | Набор 2

Эта статья предоставлена Nishant_Singh (Pintu) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Подсчитать все подстроки палиндрома в строке | Комплект 1

0.00 (0%) 0 votes