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.
Examples: 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 una solución basada en programación dinámica en la publicación a continuación. Cuente todas las substrings de Palindrome en una string | Conjunto 1 La solución discutida aquí es la extensión del problema de la substring palindrómica más larga .
La idea es que cada carácter en la string de entrada dada, lo consideremos como el punto medio de un palíndromo y lo expandamos en ambas direcciones para encontrar todos los palíndromos de longitudes pares e impares. Usamos hashmap para realizar un seguimiento de todos los palíndromos distintos de longitud superior a 1 y devolver el tamaño del mapa que cuenta con todas las substrings de palíndromos posibles.
Implementación:
CPP
// C++ program to count all distinct 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 countPalindromes(string s)
{
unordered_map<string, int> m;
for (int i = 0; i < s.length(); i++) {
// check for odd length palindromes
for (int j = 0; j <= i; j++) {
if (!s[i + j])
break;
if (s[i - j] == s[i + j]) {
// check for palindromes of length
// greater than 1
if ((i + j + 1) - (i - j) > 1)
m[s.substr(i - j,
(i + j + 1) - (i - j))]++;
} else
break;
}
// check for even length palindromes
for (int j = 0; j <= i; j++) {
if (!s[i + j + 1])
break;
if (s[i - j] == s[i + j + 1]) {
// check for palindromes of length
// greater than 1
if ((i + j + 2) - (i - j) > 1)
m[s.substr(i - j,
(i + j + 2) - (i - j))]++;
} else
break;
}
}
return m.size();
}
// Driver code
int main()
{
string s = "abbaeae";
cout << countPalindromes(s) << endl;
return 0;
}
Java
// Java Program to count palindrome substring
// in a string
public class PalindromeSubstring {
// Method which return count palindrome substring
static int countPS(String str){
String temp = "";
StringBuffer stf;
int count = 0;
// Iterate the loop twice
for (int i = 0; i < str.length(); i++) {
for (int j = i + 1; j <= str.length(); j++) {
// Get each substring
temp = str.substring(i, j);
// If length is greater than or equal to two
// Check for palindrome
if (temp.length() >= 2) {
// Use StringBuffer class to reverse the string
stf = new StringBuffer(temp);
stf.reverse();
// Compare substring with reverse of substring
if (stf.toString().compareTo(temp) == 0)
count++;
}
}
}
// return the count
return count;
}
// Driver Code
public static void main(String args[]) throws Exception {
// Declare and initialize the string
String str = "abbaeae";
// Call the method
System.out.println(countPS(str));
}
} // This code is contributes by hungundji
Python3
# Python program to count all distinct palindromic
# substrings of a string.
# Returns total number of palindrome substring of
# length greater than equal to 2
def countPalindromes(s):
m = {}
for i in range(len(s)):
# check for odd length palindromes
for j in range(i+1):
if (i + j >= len(s)):
break
if (s[i - j] == s[i + j]):
# check for palindromes of length
# greater than 1
if ((i + j + 1) - (i - j) > 1):
if(s[i - j:(i + j + 1)] in m):
m[s[i - j:(i + j + 1)]] += 1
else:
m[s[i - j:(i + j + 1)]] = 1
else:
break
# check for even length palindromes
for j in range(i+1):
if (i + j + 1 >= len(s)):
break
if (s[i - j] == s[i + j + 1]):
# check for palindromes of length
# greater than 1
if ((i + j + 2) - (i - j) > 1):
if(s[i - j:i + j + 2] in m):
m[s[i - j:(i + j + 2)]] += 1
else:
m[s[i - j:(i + j + 2)]] = 1
else:
break
return len(m)
# Driver code
s = "abbaeae"
print(countPalindromes(s))
# This code is contributed by shinjanpatra
C#
// C# Program to count palindrome substring
// in a string
using System;
class GFG
{
// Method which return count palindrome substring
static int countPS(String str)
{
String temp = "";
String stf;
int count = 0;
// Iterate the loop twice
for (int i = 0; i < str.Length; i++)
{
for (int j = i + 1;
j <= str.Length; j++)
{
// Get each substring
temp = str.Substring(i, j-i);
// If length is greater than or equal to two
// Check for palindrome
if (temp.Length >= 2)
{
// Use StringBuffer class to reverse
// the string
stf = temp;
stf = reverse(temp);
// Compare substring with reverse of substring
if (stf.ToString().CompareTo(temp) == 0)
count++;
}
}
}
// return the count
return count;
}
static String reverse(String input)
{
char[] a = input.ToCharArray();
int l, r = 0;
r = a.Length - 1;
for (l = 0; l < r; l++, r--)
{
// Swap values of l and r
char temp = a[l];
a[l] = a[r];
a[r] = temp;
}
return String.Join("",a);
}
// Driver Code
public static void Main(String []args)
{
// Declare and initialize the string
String str = "abbaeae";
// Call the method
Console.WriteLine(countPS(str));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to count all distinct palindromic
// substrings of a string.
// Returns total number of palindrome substring of
// length greater than equal to 2
function countPalindromes(s)
{
let m = new Map();
for (let i = 0; i < s.length; i++) {
// check for odd length palindromes
for (let j = 0; j <= i; j++) {
if (!s[i + j])
break;
if (s[i - j] == s[i + j]) {
// check for palindromes of length
// greater than 1
if ((i + j + 1) - (i - j) > 1){
if(m.has(s.substr(i - j,(i + j + 1) - (i - j)))){
m.set(s.substr(i - j,(i + j + 1) - (i - j)),m.get(s.substr(i - j,(i + j + 1) - (i - j))) + 1)
}
else m.set(s.substr(i - j,(i + j + 1) - (i - j)),1)
}
} else
break;
}
// check for even length palindromes
for (let j = 0; j <= i; j++) {
if (!s[i + j + 1])
break;
if (s[i - j] == s[i + j + 1]) {
// check for palindromes of length
// greater than 1
if ((i + j + 2) - (i - j) > 1){
if(m.has(s.substr(i - j,(i + j + 2) - (i - j)))){
m.set(s.substr(i - j,(i + j + 2) - (i - j)),m.get(s.substr(i - j,(i + j + 2) - (i - j))) + 1)
}
else m.set(s.substr(i - j,(i + j + 2) - (i - j)),1)
}
} else
break;
}
}
return m.size;
}
// Driver code
let s = "abbaeae"
document.write(countPalindromes(s),"</br>")
// This code is contributed by shinjanpatra
</script>
4
Complejidad temporal O(n 2 ) Espacio auxiliar O(n) Este artículo es una contribución de Ankur Singh . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
En el enfoque discutido anteriormente, estamos usando un mapa desordenado que ocupa el espacio O (n), pero podemos hacer lo mismo sin usar ningún espacio adicional. En lugar de hacer un mapa hash, podemos contar directamente la substring palindrómica.
Implementación:
C++
#include <bits/stdc++.h>
using namespace std;
int countPalindromes(string s)
{
int n = s.size();
int count = 0;
for (int i = 0; i < s.size(); i++) {
int left = i - 1;
int right = i + 1;
while (left >= 0 and right < n) {
if (s[left] == s[right])
count++;
else
break;
left--;
right++;
}
}
for (int i = 0; i < s.size(); i++) {
int left = i;
int right = i + 1;
while (left >= 0 and right < n) {
if (s[left] == s[right])
count++;
else
break;
left--;
right++;
}
}
return count;
}
int main()
{
string s = "abbaeae";
cout << countPalindromes(s) << endl;
return 0;
}
// This code is contributed by Arpit Jain
Python
# Python program to count all distinct palindromic # substrings of a string. # Returns total number of palindrome substring of # length greater than equal to 2 def countPalindromes(s): n = len(s) count = 0 for i in range(0, n): left = i-1 right = i+1 while left >= 0 and right < n: if s[left] == s[right]: count += 1 else: break left -= 1 right += 1 for i in range(0, n): left = i right = i+1 while left >= 0 and right < n: if s[left] == s[right]: count += 1 else: break left -= 1 right += 1 return count # Driver code s = "abbaeae" print(countPalindromes(s)) # This code is contributed by Arpit Jain
4
La complejidad del tiempo es O(n^2) en el peor de los casos porque estamos ejecutando un ciclo while dentro de un ciclo for porque en el ciclo while nos estamos expandiendo en ambas direcciones, por eso es O(n/2) en el peor de los casos cuando todos los caracteres son iguales, por ejemplo: «aaaaaaaa».
Pero no estamos usando ningún espacio adicional, la Complejidad espacial es O(1) .
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