Dada una string de caracteres ASCII en minúsculas, encuentre todas las substrings palindrómicas continuas distintas de la misma.
Ejemplos:
Input: str = "abaaa" Output: Below are 5 palindrome sub-strings a aa aaa aba b Input: str = "geek" Output: Below are 4 palindrome sub-strings e ee g k
Método 1:
Paso 1: Encontrar todos los palíndromos usando el algoritmo de Manacher modificado:
considerando cada carácter como un pivote, expanda en ambos lados para encontrar la longitud de los palíndromos de longitud par e impar centrados en el carácter pivote bajo consideración y almacene la longitud en las 2 arrays (impar & incluso).
La complejidad del tiempo para este paso es O(n^2)
Paso 2: Insertar todos los palíndromos encontrados en un HashMap:
Inserte todos los palíndromos encontrados en el paso anterior en un HashMap. También inserte todos los caracteres individuales de la string en HashMap (para generar substrings palindrómicas distintas de una sola letra).
La complejidad de tiempo de este paso es O(n^3) suponiendo que la búsqueda de inserción de hash toma O(1) tiempo. Tenga en cuenta que puede haber como máximo O (n ^ 2) substrings de palíndromo de una string. A continuación, se usa el código hashmap ordenado de C++ donde la complejidad de tiempo de inserción y búsqueda es O (Iniciar sesión). En C++, el hashmap ordenado se implementa mediante Red Black Tree .
Paso 3: Imprimir los distintos palíndromos y el número de tales palíndromos distintos:
El último paso es imprimir todos los valores almacenados en el HashMap (solo los elementos distintos serán procesados debido a la propiedad de HashMap). El tamaño del mapa da el número de substrings continuas palindrómicas distintas.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to find all distinct palindrome sub-strings
// of a given string
#include <iostream>
#include <map>
using namespace std;
// Function to print all distinct palindrome sub-strings of s
void palindromeSubStrs(string s)
{
map<string, int> m;
int n = s.size();
// table for storing results (2 rows for odd-
// and even-length palindromes
int R[2][n+1];
// Find all sub-string palindromes from the given input
// string insert 'guards' to iterate easily over s
s = "@" + s + "#";
for (int j = 0; j <= 1; j++)
{
int rp = 0; // length of 'palindrome radius'
R[j][0] = 0;
int i = 1;
while (i <= n)
{
// Attempt to expand palindrome centered at i
while (s[i - rp - 1] == s[i + j + rp])
rp++; // Incrementing the length of palindromic
// radius as and when we find valid palindrome
// Assigning the found palindromic length to odd/even
// length array
R[j][i] = rp;
int k = 1;
while ((R[j][i - k] != rp - k) && (k < rp))
{
R[j][i + k] = min(R[j][i - k],rp - k);
k++;
}
rp = max(rp - k,0);
i += k;
}
}
// remove 'guards'
s = s.substr(1, n);
// Put all obtained palindromes in a hash map to
// find only distinct palindromess
m[string(1, s[0])]=1;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= 1; j++)
for (int rp = R[j][i]; rp > 0; rp--)
m[s.substr(i - rp - 1, 2 * rp + j)]=1;
m[string(1, s[i])]=1;
}
//printing all distinct palindromes from hash map
cout << "Below are " << m.size()-1
<< " palindrome sub-strings";
map<string, int>::iterator ii;
for (ii = m.begin(); ii!=m.end(); ++ii)
cout << (*ii).first << endl;
}
// Driver program
int main()
{
palindromeSubStrs("abaaa");
return 0;
}
Java
// Java program to find all distinct palindrome
// sub-strings of a given string
import java.util.Map;
import java.util.TreeMap;
public class GFG
{
// Function to print all distinct palindrome
// sub-strings of s
static void palindromeSubStrs(String s)
{
//map<string, int> m;
TreeMap<String , Integer> m = new TreeMap<>();
int n = s.length();
// table for storing results (2 rows for odd-
// and even-length palindromes
int[][] R = new int[2][n+1];
// Find all sub-string palindromes from the
// given input string insert 'guards' to
// iterate easily over s
s = "@" + s + "#";
for (int j = 0; j <= 1; j++)
{
int rp = 0; // length of 'palindrome radius'
R[j][0] = 0;
int i = 1;
while (i <= n)
{
// Attempt to expand palindrome centered
// at i
while (s.charAt(i - rp - 1) == s.charAt(i +
j + rp))
rp++; // Incrementing the length of
// palindromic radius as and
// when we find valid palindrome
// Assigning the found palindromic length
// to odd/even length array
R[j][i] = rp;
int k = 1;
while ((R[j][i - k] != rp - k) && (k < rp))
{
R[j][i + k] = Math.min(R[j][i - k],
rp - k);
k++;
}
rp = Math.max(rp - k,0);
i += k;
}
}
// remove 'guards'
s = s.substring(1, s.length()-1);
// Put all obtained palindromes in a hash map to
// find only distinct palindromess
m.put(s.substring(0,1), 1);
for (int i = 1; i < n; i++)
{
for (int j = 0; j <= 1; j++)
for (int rp = R[j][i]; rp > 0; rp--)
m.put(s.substring(i - rp - 1, i - rp - 1
+ 2 * rp + j), 1);
m.put(s.substring(i, i + 1), 1);
}
// printing all distinct palindromes from
// hash map
System.out.println("Below are " + (m.size())
+ " palindrome sub-strings");
for (Map.Entry<String, Integer> ii:m.entrySet())
System.out.println(ii.getKey());
}
// Driver program
public static void main(String args[])
{
palindromeSubStrs("abaaa");
}
}
// This code is contributed by Sumit Ghosh
Python3
# Python program Find all distinct palindromic sub-strings
# of a given string
# Function to print all distinct palindrome sub-strings of s
def palindromeSubStrs(s):
m = dict()
n = len(s)
# table for storing results (2 rows for odd-
# and even-length palindromes
R = [[0 for x in range(n+1)] for x in range(2)]
# Find all sub-string palindromes from the given input
# string insert 'guards' to iterate easily over s
s = "@" + s + "#"
for j in range(2):
rp = 0 # length of 'palindrome radius'
R[j][0] = 0
i = 1
while i <= n:
# Attempt to expand palindrome centered at i
while s[i - rp - 1] == s[i + j + rp]:
rp += 1 # Incrementing the length of palindromic
# radius as and when we find valid palindrome
# Assigning the found palindromic length to odd/even
# length array
R[j][i] = rp
k = 1
while (R[j][i - k] != rp - k) and (k < rp):
R[j][i+k] = min(R[j][i-k], rp - k)
k += 1
rp = max(rp - k, 0)
i += k
# remove guards
s = s[1:len(s)-1]
# Put all obtained palindromes in a hash map to
# find only distinct palindrome
m[s[0]] = 1
for i in range(1,n):
for j in range(2):
for rp in range(R[j][i],0,-1):
m[s[i - rp - 1 : i - rp - 1 + 2 * rp + j]] = 1
m[s[i]] = 1
# printing all distinct palindromes from hash map
print ("Below are " + str(len(m)) + " pali sub-strings")
for i in m:
print (i)
# Driver program
palindromeSubStrs("abaaa")
# This code is contributed by BHAVYA JAIN and ROHIT SIKKA
C#
// C# program to find all distinct palindrome
// sub-strings of a given string
using System;
using System.Collections.Generic;
class GFG
{
// Function to print all distinct palindrome
// sub-strings of s
public static void palindromeSubStrs(string s)
{
//map<string, int> m;
Dictionary < string,
int > m = new Dictionary < string,
int > ();
int n = s.Length;
// table for storing results (2 rows for odd-
// and even-length palindromes
int[, ] R = new int[2, n + 1];
// Find all sub-string palindromes from the
// given input string insert 'guards' to
// iterate easily over s
s = "@" + s + "#";
for (int j = 0; j <= 1; j++)
{
int rp = 0; // length of 'palindrome radius'
R[j, 0] = 0;
int i = 1;
while (i <= n)
{
// Attempt to expand palindrome centered
// at i
while (s[i - rp - 1] == s[i + j + rp])
// Incrementing the length of
// palindromic radius as and
// when we find valid palindrome
rp++;
// Assigning the found palindromic length
// to odd/even length array
R[j, i] = rp;
int k = 1;
while ((R[j, i - k] != rp - k) && k < rp)
{
R[j, i + k] = Math.Min(R[j, i - k], rp - k);
k++;
}
rp = Math.Max(rp - k, 0);
i += k;
}
}
// remove 'guards'
s = s.Substring(1);
// Put all obtained palindromes in a hash map to
// find only distinct palindromess
if (!m.ContainsKey(s.Substring(0, 1)))
m.Add(s.Substring(0, 1), 1);
else
m[s.Substring(0, 1)]++;
for (int i = 1; i < n; i++)
{
for (int j = 0; j <= 1; j++)
for (int rp = R[j, i]; rp > 0; rp--)
{
if (!m.ContainsKey(s.Substring(i - rp - 1, 2 * rp + j)))
m.Add(s.Substring(i - rp - 1, 2 * rp + j), 1);
else
m[s.Substring(i - rp - 1, 2 * rp + j)]++;
}
if (!m.ContainsKey(s.Substring(i, 1)))
m.Add(s.Substring(i, 1), 1);
else
m[s.Substring(i, 1)]++;
}
// printing all distinct palindromes from
// hash map
Console.WriteLine("Below are " + (m.Count));
foreach(KeyValuePair < string, int > ii in m)
Console.WriteLine(ii.Key);
}
// Driver Code
public static void Main(string[] args)
{
palindromeSubStrs("abaaa");
}
}
// This code is contributed by
// sanjeev2552
Javascript
<script>
// JavaScript program to find all distinct palindrome sub-strings
// of a given string
// Function to print all distinct palindrome sub-strings of s
function palindromeSubStrs(s)
{
let m = new Map();
let n = s.length;
// table for storing results (2 rows for odd-
// and even-length palindromes
let R = new Array(2);
for(let i = 0; i < 2; i++)
R[i] = new Array(n + 1);
// Find all sub-string palindromes from the given input
// string insert 'guards' to iterate easily over s
s = "@" + s + "#";
for (let j = 0; j <= 1; j++)
{
let rp = 0; // length of 'palindrome radius'
R[j][0] = 0;
let i = 1;
while (i <= n)
{
// Attempt to expand palindrome centered at i
while (s[i - rp - 1] == s[i + j + rp])
rp++; // Incrementing the length of palindromic
// radius as and when we find valid palindrome
// Assigning the found palindromic length to odd/even
// length array
R[j][i] = rp;
let k = 1;
while ((R[j][i - k] != rp - k) && (k < rp))
{
R[j][i + k] = Math.min(R[j][i - k],rp - k);
k++;
}
rp = Math.max(rp - k,0);
i += k;
}
}
// remove 'guards'
s = s.substring(1, n+1);
// Put all obtained palindromes in a hash map to
// find only distinct palindromes
m.set(`${s[0]}`,1);
for (let i = 1; i < n; i++)
{
for (let j = 0; j <= 1; j++){
for (let rp = R[j][i]; rp > 0; rp--){
m.set(s.substring(i - rp - 1, i + rp + j-1),1);
}
}
m.set(`${s[i]}`,1);
}
// printing all distinct palindromes from hash map
document.write(`Below are ${m.size} palindrome sub-strings`,"</br>");
for(let [x, y] of m)
document.write(x,"</br>");
}
// Driver program
palindromeSubStrs("abaaa");
// This code is contributed by shinjanpatra
</script>
Producción:
Below are 5 palindrome sub-strings a aa aaa aba b
Método 2:
Longitud de la cuerda – N
Paso 1: encuentre todas las substrings palindrómicas
Primero, para cada substring, verifique si es palíndromo o no usa una programación dinámica como esta: https://www.geeksforgeeks.org/count-palindrome-sub-strings-string/
Complejidad de tiempo – O(N 2 ) y Complejidad de espacio – O(N 2 )
Paso 2: Eliminar palíndromos duplicados
Para cada índice a partir del índice 0, usaremos el algoritmo KMP y verificaremos si el prefijo y el sufijo son iguales y si es palíndromo, luego pondremos 0 en la array dp para esa substring de sufijo.
Complejidad de tiempo O(N 2 ) y complejidad de espacio O(N) para array KMP
Paso 3: Imprima los distintos palíndromos y el número de tales palíndromos
Para cada substring, compruebe si está presente en la array dp (es decir, dp[i][j] == true) e imprímala.
Complejidad temporal O(N 2 ) y Complejidad espacial O(N)
Complejidad total del tiempo – O(N 2 )
Complejidad total del espacio – O(N 2 )
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to find all distinct palindrome sub-strings
// of a given string
#include <iostream>
#include <vector>
using namespace std;
int solve(string s)
{
int n = s.size();
// dp array to store whether a substring is palindrome
// or not using dynamic programming we can solve this
// in O(N^2)
// dp[i][j] will be true (1) if substring (i, j) is
// palindrome else false (0)
vector<vector<bool> > dp(n, vector<bool>(n, false));
for (int i = 0; i < n; i++) {
// base case every char is palindrome
dp[i][i] = 1;
// check for every substring of length 2
if (i < n && s[i] == s[i + 1]) {
dp[i][i + 1] = 1;
}
}
// check every substring of length greater than 2 for
// palindrome
for (int len = 3; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
if (s[i] == s[i + (len - 1)]
&& dp[i + 1][i + (len - 1) - 1]) {
dp[i][i + (len - 1)] = true;
}
}
}
//*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
// here we will apply kmp algorithm for substrings
// starting from i = 0 to n-1 when we will find prefix
// and suffix of a substring to be equal and it is
// palindrome we will make dp[i][j] for that suffix to be
// false which means it is already added in the prefix
// and we should not count it anymore.
vector<int> kmp(n, 0);
for (int i = 0; i < n; i++) {
// starting kmp for every i form 0 to n-1
int j = 0, k = 1;
while (k + i < n) {
if (s[j + i] == s[k + i]) {
// make suffix to be false
// if this suffix is palindrome then it is
// already included in prefix
dp[k + i - j][k + i] = false;
kmp[k++] = ++j;
}
else if (j > 0) {
j = kmp[j - 1];
}
else {
kmp[k++] = 0;
}
}
}
//*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
int count = 0;
for (int i = 0; i < n; i++) {
string str;
for (int j = i; j < n; j++) {
str += s[j];
if (dp[i][j]) {
// count number of resultant distinct
// substrings and print that substring
count++;
cout << str << '\n';
}
}
}
cout << "Total number of distinct palindromes is "
<< count << '\n';
return 0;
}
// Driver code starts
// This code is contributed by Aditya Anand
int main()
{
string s1 = "abaaa", s2 = "aaaaaaaaaa";
solve(s1);
solve(s2);
return 0;
}
// Driver code ends
a aba b aa aaa Total number of distinct palindromes is 5 a aa aaa aaaa aaaaa aaaaaa aaaaaaa aaaaaaaa aaaaaaaaa aaaaaaaaaa Total number of distinct palindromes is 10
Problema similar:
Cuente todas las substrings de Palindrome en una string Vignesh Narayanan y Sowmya Sampath
contribuyeron con este artículo . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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