Cuente todas las substrings de Palindrome en una string | Serie 1

Dada una string, la tarea es contar todas las substrings de palíndromo en una string dada. La longitud de la substring del palíndromo es mayor o igual a 2. 

Ejemplos:

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"

Hemos discutido un problema similar a continuación. 
Encuentre todas las substrings palindrómicas distintas de una string dada

El problema anterior se puede definir recursivamente. 

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]
   // this condition shows that in recursion if i crosses
   // j then it will be a invalid substring or
   // if i==j that means only one character is remaining 
   // and we require substring of length 2 
   //in both the conditions we need to return 0
   Else if(i == j ||  i > j) return 0;
   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);

Si dibujamos el árbol recursivo de la solución recursiva anterior, podemos observar subproblemas superpuestos . Dado que el problema tiene subproblemas superpuestos, podemos resolverlo de manera eficiente utilizando la programación dinámica. 

A continuación se muestra una solución basada en programación dinámica. 

C++

// C++ program to find palindromic substrings of a string
#include <bits/stdc++.h>
using namespace std;
  
// Returns total number of palindrome substring of
// length greater than equal to 2
int CountPS(char str[], int n)
{
   //to store the count of palindrome subarrays
  int ans=0;
  
    // P[i][j] = true if substring str[i..j] is palindrome,
    // else false
    bool P[n][n];
    memset(P, false, sizeof(P));
  
    // palindrome of single length
    for (int i = 0; i < n; i++){
        P[i][i] = true;
    }
  
  
    // Palindromes of length more than or equal to 2. We start with
    // a gap of length 1 and fill the DP table in a way that
    // gap between starting and ending indexes increases one
    // by one by outer loop.
    for (int gap = 2; gap <=n; gap++) {
        // Pick starting point for current gap
        for (int i = 0; i <= n-gap; i++) {
            // Set ending point
            int j = gap + i-1;
  
            // check If current string is palindrome of length 2
            if(i==j-1){
              P[i][j]=(str[i]==str[j]);
            }else {
              //check if the current substring is palindrome of length more than 2 
              //if characters at index i,j are equal check for string in between them 
              //from i+1 to j-1 if it is palindrome or not
              P[i][j]=(str[i]==str[j] && P[i+1][j-1]);
            }
          //if substring from index i to j is palindrome increase the count
          if(P[i][j]){
            ans++;
          }
        }
    }
  
    // return total palindromic substrings
    return ans;
}
  
// Driver code
int main()
{
    char str[] = "abaab";
    int n = strlen(str);
    cout << CountPS(str, n) << endl;
    return 0;
}

Java

// Java program to find palindromic substrings of a string
  
public class GFG {
    // Returns total number of palindrome substring of
    // length greater than equal to 2
    static int CountPS(char str[], int n)
    {
        // create empty 2-D matrix that counts all
        // palindrome substring. dp[i][j] stores counts of
        // palindromic substrings in st[i..j]
        int dp[][] = new int[n][n];
  
        // P[i][j] = true if substring str[i..j] is
        // palindrome, else false
        boolean P[][] = new boolean[n][n];
  
        // palindrome of single length
        for (int i = 0; i < n; i++)
            P[i][i] = true;
  
        // palindrome of length 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;
            }
        }
  
        // Palindromes of length more than 2. This loop is
        // similar to Matrix Chain Multiplication. We start
        // with a gap of length 2 and fill the DP table in a
        // way that gap between starting and ending indexes
        // increases one by one by outer loop.
        for (int gap = 2; gap < n; gap++) {
            // Pick starting point for current gap
            for (int i = 0; i < n - gap; i++) {
                // Set ending point
                int j = gap + i;
  
                // If current string is palindrome
                if (str[i] == str[j] && P[i + 1][j - 1])
                    P[i][j] = true;
  
                // Add current palindrome substring ( + 1)
                // and rest palindrome substring (dp[i][j-1]
                // + dp[i+1][j]) remove common palindrome
                // substrings (- 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 total palindromic substrings
        return dp[0][n - 1];
    }
  
    // Driver code
    public static void main(String[] args)
    {
        String str = "abaab";
        System.out.println(
            CountPS(str.toCharArray(), str.length()));
    }
}

Python3

# Python3 program to find palindromic
# substrings of a string
  
# Returns total number of palindrome
# substring of length greater than
# equal to 2
  
  
def CountPS(str, n):
  
    # create empty 2-D matrix that counts
    # all palindrome substring. dp[i][j]
    # stores counts of palindromic
    # substrings in st[i..j]
    dp = [[0 for x in range(n)]
          for y in range(n)]
  
    # P[i][j] = true if substring str[i..j]
    # is palindrome, else false
    P = [[False for x in range(n)]
         for y in range(n)]
  
    # palindrome of single length
    for i in range(n):
        P[i][i] = True
  
    # palindrome of length 2
    for i in range(n - 1):
        if (str[i] == str[i + 1]):
            P[i][i + 1] = True
            dp[i][i + 1] = 1
  
    # Palindromes of length more than 2. This
    # loop is similar to Matrix Chain Multiplication.
    # We start with a gap of length 2 and fill DP
    # table in a way that the gap between starting and
    # ending indexes increase one by one by
    # outer loop.
    for gap in range(2, n):
  
        # Pick a starting point for the current gap
        for i in range(n - gap):
  
            # Set ending point
            j = gap + i
  
            # If current string is palindrome
            if (str[i] == str[j] and P[i + 1][j - 1]):
                P[i][j] = True
  
            # Add current palindrome substring ( + 1)
            # and rest palindrome substring (dp[i][j-1] +
            # dp[i+1][j]) remove common palindrome
            # substrings (- 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 total palindromic substrings
    return dp[0][n - 1]
  
  
# Driver Code
if __name__ == "__main__":
  
    str = "abaab"
    n = len(str)
    print(CountPS(str, n))
  
# This code is contributed by ita_c

C#

// C# program to find palindromic
// substrings of a string
using System;
  
class GFG {
    // Returns total number of
    // palindrome substring of
    // length greater than equal to 2
    public static int CountPS(char[] str, int n)
    {
        // create empty 2-D matrix that counts
        // all palindrome substring. dp[i][j]
        // stores counts of palindromic
        // substrings in st[i..j]
  
        int[][] dp
            = RectangularArrays.ReturnRectangularIntArray(
                n, n);
  
        // P[i][j] = true if substring str[i..j]
        // is palindrome, else false
  
        bool[][] P
            = RectangularArrays.ReturnRectangularBoolArray(
                n, n);
  
        // palindrome of single length
        for (int i = 0; i < n; i++) {
            P[i][i] = true;
        }
  
        // palindrome of length 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;
            }
        }
  
        // Palindromes of length more then 2.
        // This loop is similar to Matrix Chain
        // Multiplication. We start with a gap
        // of length 2 and fill DP table in a
        // way that gap between starting and
        // ending indexes increases one by one
        // by outer loop.
        for (int gap = 2; gap < n; gap++) {
            // Pick starting point for current gap
            for (int i = 0; i < n - gap; i++) {
                // Set ending point
                int j = gap + i;
  
                // If current string is palindrome
                if (str[i] == str[j] && P[i + 1][j - 1]) {
                    P[i][j] = true;
                }
  
                // Add current palindrome substring
                // ( + 1) and rest palindrome substring
                // (dp[i][j-1] + dp[i+1][j]) remove common
                // palindrome substrings (- 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 total palindromic substrings
        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;
        }
    }
  
    // Driver Code
    public static void Main(string[] args)
    {
        string str = "abaab";
        Console.WriteLine(
            CountPS(str.ToCharArray(), str.Length));
    }
}
  
// This code is contributed by Shrikant13

PHP

<?php
// PHP program to find palindromic substrings
// of a string 
  
// Returns total number of palindrome 
// substring of length greater than equal to 2 
function CountPS($str, $n) 
{ 
    // create empty 2-D matrix that counts
    // all palindrome substring. dp[i][j] 
    // stores counts of palindromic 
    // substrings in 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 if substring str[i..j]  
    // is palindrome, else false 
    $P = array(array());
        for ($i = 0; $i < $n; $i++)
            for($j = 0; $j < $n; $j++)
                $P[$i][$j] = false;
  
    // palindrome of single length 
    for ($i= 0; $i< $n; $i++) 
        $P[$i][$i] = true; 
  
    // palindrome of length 2 
    for ($i = 0; $i < $n - 1; $i++) 
    { 
        if ($str[$i] == $str[$i + 1]) 
        { 
            $P[$i][$i + 1] = true; 
            $dp[$i][$i + 1] = 1; 
        } 
    } 
  
    // Palindromes of length more then 2. This 
    // loop is similar to Matrix Chain Multiplication.
    // We start with a gap of length 2 and fill DP 
    // table in a way that gap between starting and 
    // ending indexes increases one by one by 
    // outer loop. 
    for ($gap = 2; $gap < $n; $gap++) 
    { 
        // Pick starting point for current gap 
        for ($i = 0; $i < $n - $gap; $i++) 
        { 
            // Set ending point 
            $j = $gap + $i; 
  
            // If current string is palindrome 
            if ($str[$i] == $str[$j] && $P[$i + 1][$j - 1]) 
                $P[$i][$j] = true; 
  
            // Add current palindrome substring (+ 1) 
            // and rest palindrome substring (dp[i][j-1] + 
            // dp[i+1][j]) remove common palindrome
            // substrings (- 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 total palindromic substrings 
    return $dp[0][$n - 1]; 
} 
  
// Driver Code 
$str = "abaab"; 
$n = strlen($str); 
echo CountPS($str, $n);
  
// This code is contributed by Ryuga
?>

Javascript

<script>
  
// Javascript program to find palindromic substrings of a string
      
    // Returns total number of palindrome substring of
    // length greater than equal to 2
    function CountPS(str,n)
    {
        // create empty 2-D matrix that counts all
        // palindrome substring. dp[i][j] stores counts of
        // palindromic substrings in st[i..j]
        let dp=new Array(n);
          
        // P[i][j] = true if substring str[i..j] is
        // palindrome, else false
        let P=new Array(n);
          
        for(let i=0;i<n;i++)
        {
            dp[i]=new Array(n);
            P[i]=new Array(n);
            for(let j=0;j<n;j++)
            {
                dp[i][j]=0;
                P[i][j]=false;
            }
        }
          
        // palindrome of single length
        for (let i = 0; i < n; i++)
            P[i][i] = true;
   
        // palindrome of length 2
        for (let i = 0; i < n - 1; i++) {
            if (str[i] == str[i + 1]) {
                P[i][i + 1] = true;
                dp[i][i + 1] = 1;
            }
        }
   
        // Palindromes of length more than 2. This loop is
        // similar to Matrix Chain Multiplication. We start
        // with a gap of length 2 and fill the DP table in a
        // way that gap between starting and ending indexes
        // increases one by one by outer loop.
        for (let gap = 2; gap < n; gap++) {
            // Pick starting point for current gap
            for (let i = 0; i < n - gap; i++) {
                // Set ending point
                let j = gap + i;
   
                // If current string is palindrome
                if (str[i] == str[j] && P[i + 1][j - 1])
                    P[i][j] = true;
   
                // Add current palindrome substring ( + 1)
                // and rest palindrome substring (dp[i][j-1]
                // + dp[i+1][j]) remove common palindrome
                // substrings (- 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 total palindromic substrings
        return dp[0][n - 1];
    }
      
    // Driver code
    let str = "abaab";
    document.write(
            CountPS(str.split(""), str.length));
      
    // This code is contributed by avanitrachhadiya2155
      
</script>
Producción

3

Complejidad temporal: O(n 2
Espacio auxiliar: O(n 2

Método 2: este enfoque utiliza Top Down DP, es decir, una versión memorizada de la recursividad.

Recursive soln:
1. Here base condition comes out to be i>j if we hit this condition, return 1.
2. We check for each and every i and j, if the characters are equal, 
   if that is not the case, return 0.
3. Call the is_palindrome function again with incremented i  and decremented j.
4. Check this for all values of i and j by applying 2 for loops.

Implementación:

C++

#include <bits/stdc++.h>
using namespace std;
  
int dp[1001][1001]; // 2D matrix
bool isPal(string s, int i, int j)
{
    // Base condition
    if (i > j)
        return 1;
  
    // check if the recursive tree
    // for given i, j
    // has already been executed
    if (dp[i][j] != -1)
        return dp[i][j];
  
    // If first and last characters of 
    // substring are unequal
    if (s[i] != s[j])
        return dp[i][j] = 0;
  
    // memoization
    return dp[i][j] = isPal(s, i + 1, j - 1); 
}
  
int countSubstrings(string s)
{
    memset(dp, -1, sizeof(dp));
    int n = s.length();
    int count = 0;
  
    // 2 for loops are required to check for
    // all the palindromes in the string.
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++) 
        {
            // Increment count for every palindrome
            if (isPal(s, i, j))
                count++;
        }
    }
    // return total palindromic substrings
    return count;
}
  
// Driver code
int main()
{
  
    string s = "abbaeae";
  
    cout << countSubstrings(s);
  
    //"bb" , "abba" ,"aea", "eae" are
    // the 4 palindromic substrings.
  
    // This code is contributed by Bhavneet Singh
  
    return 0;
}

Java

import java.util.*;
public class Main
{
    static int dp[][] = new int[1001][1001]; // 2D matrix
      
    public static int isPal(String s, int i, int j)
    {
        // Base condition
        if (i > j)
            return 1;
       
        // check if the recursive tree
        // for given i, j
        // has already been executed
        if (dp[i][j] != -1)
            return dp[i][j];
       
        // If first and last characters of 
        // substring are unequal
        if (s.charAt(i) != s.charAt(j))
            return dp[i][j] = 0;
       
        // memoization
        return dp[i][j] = isPal(s, i + 1, j - 1); 
    }
       
    public static int countSubstrings(String s)
    {
        for (int[] row: dp)
        {
            Arrays.fill(row, -1);
        }
        int n = s.length();
        int count = 0;
       
        // 2 for loops are required to check for
        // all the palindromes in the string.
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++) 
            {
                // Increment count for every palindrome
                if (isPal(s, i, j) != 0)
                    count++;
            }
        }
        
        // return total palindromic substrings
        return count;
    }
  
    public static void main(String[] args) {
        String s = "abbaeae";
   
        System.out.println(countSubstrings(s));
    }
}
  
// This code is contributed by divyeshrabadiya07

Python3

# 2D matrix
dp = [[-1 for i in range(1001)] 
          for j in range(1001)]
  
def isPal(s, i, j):
      
    # Base condition
    if (i > j):
        return 1
  
    # Check if the recursive tree
    # for given i, j
    # has already been executed
    if (dp[i][j] != -1):
        return dp[i][j]
  
    # If first and last characters of 
    # substring are unequal
    if (s[i] != s[j]):
        dp[i][j] = 0
        return dp[i][j]
          
    # Memoization
    dp[i][j] = isPal(s, i + 1, j - 1)
      
    return dp[i][j]
  
def countSubstrings(s):
      
    n = len(s)
  
    count = 0
  
    # 2 for loops are required to check for
    # all the palindromes in the string.
    for i in range(n):
        for j in range(i + 1, n):
              
            # Increment count for every palindrome
            if (isPal(s, i, j)):
                count += 1
  
    # Return total palindromic substrings
    return count
  
# Driver code
s = "abbaeae"
  
print(countSubstrings(s))
  
# This code is contributed by rag2127

C#

using System;
  
class GFG{
  
// 2D matrix
static int[,] dp = new int[1001, 1001]; 
  
static int isPal(string s, int i, int j)
{
      
    // Base condition
    if (i > j)
        return 1;
    
    // Check if the recursive tree
    // for given i, j
    // has already been executed
    if (dp[i, j] != -1)
        return dp[i, j];
    
    // If first and last characters of 
    // substring are unequal
    if (s[i] != s[j])
        return dp[i, j] = 0;
    
    // Memoization
    return dp[i, j] = isPal(s, i + 1, j - 1); 
}
    
static int countSubstrings(string s)
{
    for(int i = 0; i < 1001; i++)
    {
        for(int j = 0; j < 1001; j++)
        {
            dp[i, j] = -1;
        }
    }
      
    int n = s.Length;
    int count = 0;
    
    // 2 for loops are required to check for
    // all the palindromes in the string.
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++) 
        {
              
            // Increment count for every palindrome
            if (isPal(s, i, j) != 0)
                count++;
        }
    }
      
    // Return total palindromic substrings
    return count;
}
  
// Driver Code    
static void Main()
{
    string s = "abbaeae";
      
    Console.WriteLine(countSubstrings(s));
}
}
  
// This code is contributed by divyesh072019

Javascript

<script>
    var dp = Array(1001).fill().map(()=>Array(1001).fill(-1)); // 2D matrix
  
    function isPal( s , i , j) 
    {
      
        // Base condition
        if (i > j)
            return 1;
  
        // check if the recursive tree
        // for given i, j
        // has already been executed
        if (dp[i][j] != -1)
            return dp[i][j];
  
        // If first and last characters of
        // substring are unequal
        if (s.charAt(i) != s.charAt(j))
            return dp[i][j] = 0;
  
        // memoization
        return dp[i][j] = isPal(s, i + 1, j - 1);
    }
  
    function countSubstrings( s) {
          
        var n = s.length;
        var count = 0;
  
        // 2 for loops are required to check for
        // all the palindromes in the string.
        for (i = 0; i < n; i++) {
            for (j = i + 1; j < n; j++) {
                // Increment count for every palindrome
                if (isPal(s, i, j) != 0)
                    count++;
            }
        }
  
        // return total palindromic substrings
        return count;
    }
  
    // Driver code
        var s = "abbaeae";
        document.write(countSubstrings(s));
      
// This code is contributed by Rajput-Ji
</script>
Producción

4

Cuente todas las substrings de Palindrome en una string | conjunto 2

Este artículo es una contribución de Nishant_Singh (Pintu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *