Dada una string, la tarea es encontrar todas las substrings palindrómicas de la string dada.
En el Conjunto – 1 , ya se ha discutido otro enfoque que considera solo substrings distintas, pero en estas substrings iguales, es decir, ll y ll se consideran como dos substrings, no como una.
Ejemplos:
Entrada: hellolle
Salida: 13
[h, e, l, ll, l, o, lol, lloll, ellolle, l, ll, l, e]
Explicación:
1) ellolle
2) ll, ll – Tenga en cuenta que se trata de dos substrings que solo resultan ser iguales
3) lol y lloll
4) Y, por supuesto, cada letra puede considerarse un palíndromo, las 8.
Entrada: geeksforgeeks
Salida: 15
[g, e, ee, e, k, s, f, o, r, g, e, ee, e, k, s]
Enfoque:
1- Podemos tener dos tipos de cuerdas de palíndromo que necesitamos manejar -Longitud par -Longitud impar
2- La idea es considerar un punto medio y seguir buscando la cuerda de palíndromo comparando los elementos de la izquierda y los elementos a la derecha aumentando la distancia o palindromeRadius de uno en uno hasta que no coincidan.
3- El algoritmo maneja los escenarios de palíndromo de longitud par e impar en un solo paso.
4- El pivote comienza desde 0 y se mueve hasta el final con un tamaño de paso de 0,5.
…….a) cuando el pivote es un valor no fraccionario, entonces los valores de palindromeRadius son integrales a partir de 0.
…….b) cuando el pivote es un valor fraccionario, entonces los valores de palindromeRadius son como 0.5, 1.5, 2.5, 3.5 ..
5- Entonces, cada vez que obtenemos una coincidencia de palíndromo, la ponemos en una lista (para que los valores duplicados se conserven porque cada substring duplicada se obtiene mediante una combinación diferente de posiciones alfabéticas)
C++
// c++ program to Count number of ways we
// can get palindrome string from a given
// string
#include<bits/stdc++.h>
using namespace std;
// function to find the substring of the
// string
string substring(string s,int a,int b)
{
string s1="";
// extract the specified position of
// the string
for(int i = a; i < b; i++)
s1 = s1 + s[i];
return s1;
}
// can get palindrome string from a
// given string
vector<string> allPalindromeSubstring(string s)
{
vector<string> v ;
// moving the pivot from starting till
// end of the string
for (float pivot = 0; pivot < s.length();
pivot += .5)
{
// set radius to the first nearest
// element on left and right
float palindromeRadius = pivot -
(int)pivot;
// if the position needs to be
// compared has an element and the
// characters at left and right
// matches
while ((pivot + palindromeRadius)
< s.length() && (pivot - palindromeRadius)
>= 0 && s[((int)(pivot - palindromeRadius))]
== s[((int)(pivot + palindromeRadius))])
{
v.push_back(substring(s,(int)(pivot -
palindromeRadius), (int)(pivot
+ palindromeRadius + 1)));
// increasing the radius by 1 to point
// to the next elements in left and right
palindromeRadius++;
}
}
return v;
}
// Driver code
int main()
{
vector <string> v =
allPalindromeSubstring("hellolle");
cout << v.size() << endl;
for(int i = 0; i < v.size(); i++)
cout << v[i] << ",";
cout << endl;
v = allPalindromeSubstring("geeksforgeeks");
cout << v.size() << endl;
for(int i = 0; i < v.size(); i++)
cout << v[i] << ",";
}
// This code is contributed by Arnab Kundu.
Java
// Java program to Count number of ways we
// can get palindrome string from a given string
import java.util.ArrayList;
import java.util.List;
public class AllPalindromeSubstringsPossible {
public static List<String> allPalindromeSubstring(String s)
{
List<String> list = new ArrayList<String>();
// moving the pivot from starting till end of the string
for (float pivot = 0; pivot < s.length(); pivot += .5) {
// set radius to the first nearest element
// on left and right
float palindromeRadius = pivot - (int)pivot;
// if the position needs to be compared has an element
// and the characters at left and right matches
while ((pivot + palindromeRadius) < s.length()
&& (pivot - palindromeRadius) >= 0
&& s.charAt((int)(pivot - palindromeRadius))
== s.charAt((int)(pivot + palindromeRadius))) {
list.add(s.substring((int)(pivot - palindromeRadius),
(int)(pivot + palindromeRadius + 1)));
// increasing the radius by 1 to point to the
// next elements in left and right
palindromeRadius++;
}
}
return list;
}
// Drivers code
public static void main(String[] args)
{
List<String> list = allPalindromeSubstring("hellolle");
System.out.println(list.size());
System.out.println(list);
list = allPalindromeSubstring("geeksforgeeks");
System.out.println(list.size());
System.out.println(list);
}
}
Python3
# Python3 program to Count number of ways we
# can get palindrome string from a given
# string
# function to find the substring of the
# string
def substring(s, a, b):
s1 = ""
# extract the specified position of
# the string
for i in range(a, b, 1):
s1 += s[i]
return s1
# can get palindrome string from a
# given string
def allPalindromeSubstring(s):
v = []
# moving the pivot from starting till
# end of the string
pivot = 0.0
while pivot < len(s):
# set radius to the first nearest
# element on left and right
palindromeRadius = pivot - int(pivot)
# if the position needs to be
# compared has an element and the
# characters at left and right
# matches
while ((pivot + palindromeRadius) < len(s) and
(pivot - palindromeRadius) >= 0 and
(s[int(pivot - palindromeRadius)] ==
s[int(pivot + palindromeRadius)])):
v.append(s[int(pivot - palindromeRadius):
int(pivot + palindromeRadius + 1)])
# increasing the radius by 1 to point
# to the next elements in left and right
palindromeRadius += 1
pivot += 0.5
return v
# Driver Code
if __name__ == "__main__":
v = allPalindromeSubstring("hellolle")
print(len(v))
print(v)
v = allPalindromeSubstring("geeksforgeeks")
print(len(v))
print(v)
# This code is contributed by
# sanjeev2552
C#
// C# program to Count number of ways we
// can get palindrome string from a given string
using System;
using System.Collections.Generic;
public class AllPalindromeSubstringsPossible
{
public static List<String> allPalindromeSubstring(String s)
{
List<String> list = new List<String>();
// moving the pivot from starting till end of the string
for (float pivot = 0; pivot < s.Length; pivot+= (float).5)
{
// set radius to the first nearest element
// on left and right
float palindromeRadius = pivot - (int)pivot;
// if the position needs to be compared has an element
// and the characters at left and right matches
while ((pivot + palindromeRadius) < s.Length
&& (pivot - palindromeRadius) >= 0
&& s[(int)(pivot - palindromeRadius)]
== s[(int)(pivot + palindromeRadius)])
{
list.Add(s.Substring((int)(pivot - palindromeRadius),
(int)(pivot + palindromeRadius + 1)-
(int)(pivot - palindromeRadius)));
// increasing the radius by 1 to point to the
// next elements in left and right
palindromeRadius++;
}
}
return list;
}
// Drivers code
public static void Main(String[] args)
{
List<String> list = allPalindromeSubstring("hellolle");
Console.WriteLine(list.Count);
for(int i = 0; i < list.Count; i++)
Console.Write(list[i]+",");
list = allPalindromeSubstring("geeksforgeeks");
Console.WriteLine("\n"+list.Count);
for(int i = 0; i < list.Count; i++)
Console.Write(list[i]+",");
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// JavaScript program to Count number of ways we
// can get palindrome string from a given string
function allPalindromeSubstring(s)
{
let list = [];
// moving the pivot from starting till end of the string
for (let pivot = 0; pivot < s.length; pivot += .5) {
// set radius to the first nearest element
// on left and right
let palindromeRadius = pivot - Math.floor(pivot);
// if the position needs to be compared has an element
// and the characters at left and right matches
while ((pivot + palindromeRadius) < s.length
&& (pivot - palindromeRadius) >= 0
&& s[(Math.floor(pivot - palindromeRadius))]
== s[Math.floor(pivot + palindromeRadius)])
{
list.push(s.substring(Math.floor(pivot -
palindromeRadius),
Math.floor(pivot + palindromeRadius + 1)));
// increasing the radius by 1 to point to the
// next elements in left and right
palindromeRadius++;
}
}
return list;
}
// Drivers code
let list = allPalindromeSubstring("hellolle");
document.write(list.length+"<br>");
document.write("["+list.join(", ")+"]<br>");
list = allPalindromeSubstring("geeksforgeeks");
document.write(list.length+"<br>");
document.write("["+list.join(", ")+"]<br>");
// This code is contributed by avanitrachhadiya2155
</script>
13 [h, e, l, ll, l, o, lol, lloll, ellolle, l, ll, l, e] 15 [g, e, ee, e, k, s, f, o, r, g, e, ee, e, k, s]
Complejidad del tiempo : O(n 3 )
Espacio Auxiliar: O(n)
Nota: Para imprimir substrings distintas, use Set ya que solo toma elementos distintos.
Este artículo es una contribución de Aarti_Rathi . 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.
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 Prasun Mondal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA