Requisitos previos: algoritmo Z
Dada una string S , la tarea es encontrar el número máximo de palíndromos que se pueden formar después de realizar los pasos dados:
- Elija un prefijo P no vacío y una substring T no vacía de igual longitud.
- Invierte P o T y concatenalos.
Nota: P y T pueden superponerse.
Ejemplos:
Entrada: S = “abab”
Salida : 6
Explicación:
Considere el prefijo como S[0 : 1] (= “ ab ”) e invierta la substring S[2 : 3] . La string resultante después de concatenar el prefijo con la substring invertida es «abba» , que es un palíndromo.
Todos los prefijos posibles son [“a”, “ab”, ”aba”, ”abab”] .
Todos los sufijos posibles son [“a”, ”b”, ”a”, ”b”, ”ab”, ”ba”, ”ab”, ”aba”, ”bab”, ”abab”] .
Por lo tanto, todos los palíndromos posibles son [“aa”, ”aa”, ”abba”, ”abba”, ”abaaba”, ”ababbaba”] .Entrada: S = “abcd”
Salida: 4
Enfoque ingenuo: genere todos los prefijos posibles y todas las substrings posibles . Concatene todos los pares de prefijos y substrings de igual longitud (después de invertirlos) y verifique si la string obtenida es palíndromo o no .
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(N 2 )
Enfoque eficiente: el enfoque anterior se puede optimizar en función de la observación de que la longitud de las strings concatenadas siempre será uniforme. Por lo tanto, solo se deben considerar aquellas strings en las que la primera mitad es la imagen especular de la segunda mitad. Por lo tanto, el problema se reduce a contar substrings para cada prefijo posible que sea igual a ese prefijo , lo que se puede hacer usando la función Z.
La función z sobre una string devolverá una array Z[] donde Z[i] representa la longitud del prefijo más largo que es igual a la substring que comienza en la posición i y termina en la posición i+Z[i] . Por lo tanto, el conteo será
.
Siga los pasos a continuación para resolver el problema:
- La idea es mantener un intervalo [l, r] que es el intervalo con max r tal que [l, r] es una substring de prefijo (substring que también es prefijo).
- Si i ≤ r , entonces Z[i] es igual al mínimo de r – i + 1 y Z[i – 1].
- Ahora, incremente Z[i] hasta que i + Z[i] sea menor que N y el carácter en el índice Z[i] e i + Z[i] sean iguales en la string dada.
- Ahora, si i + Z[i] – 1 > r , entonces establezca l en i y r en i + Z[i] – 1 .
- Repita los pasos anteriores para i de 0 a N-1 .
- La respuesta es la suma de Z[i] + 1 para cada i (0 ≤ i ≤ N-1) .
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the
// number of palindromes
int countPalindromes(string S)
{
int N = (int)S.length();
vector<int> Z(N);
// Calculation of Z-array
int l = 0, r = 0;
for (int i = 1; i < N; i++) {
if (i <= r)
Z[i] = min(r - i + 1, Z[i - l]);
while (i + Z[i] < N
&& S[Z[i]] == S[i + Z[i]]) {
Z[i]++;
}
if (i + Z[i] - 1 > r) {
l = i;
r = i + Z[i] - 1;
}
}
// Calculation of sigma(Z[i]+1)
int sum = 0;
for (int i = 0; i < Z.size(); i++) {
sum += Z[i] + 1;
}
// Return the count
return sum;
}
// Driver Code
int main()
{
// Given String
string S = "abab";
cout << countPalindromes(S);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to calculate the
// number of palindromes
static int countPalindromes(String S)
{
int N = (int)S.length();
int[] Z = new int[(N)];
// Calculation of Z-array
int l = 0, r = 0;
for(int i = 1; i < N; i++)
{
if (i <= r)
Z[i] = Math.min(r - i + 1,
Z[i - l]);
while (i + Z[i] < N &&
S.charAt(Z[i]) ==
S.charAt(i + Z[i]))
{
Z[i]++;
}
if (i + Z[i] - 1 > r)
{
l = i;
r = i + Z[i] - 1;
}
}
// Calculation of sigma(Z[i]+1)
int sum = 0;
for(int i = 0; i < Z.length; i++)
{
sum += Z[i] + 1;
}
// Return the count
return sum;
}
// Driver Code
public static void main (String[] args)
{
// Given String
String S = "abab";
System.out.println(countPalindromes(S));
}
}
// This code is contributed by code_hunt
Python3
# Python3 program the above approach # Function to calculate the # number of palindromes def countPalindrome(S): N = len(S) Z = [0] * N # Calculation of Z-array l = 0 r = 0 for i in range(1, N): if i <= r: Z[i] = min(r - i + 1, Z[i - 1]) while((i + Z[i]) < N and (S[Z[i]] == S[i + Z[i]])): Z[i] += 1 if ((i + Z[i] - 1) > r): l = ir = i + Z[i] - 1 # Calculation of sigma(Z[i]+1) sum = 0 for i in range(0, len(Z)): sum += Z[i] + 1 # return the count return sum # Driver code # Given String S = "abab" print(countPalindrome(S)) # This code is contributed by virusbuddah
C#
// C# program for the above approach
using System;
public class GFG{
// Function to calculate the
// number of palindromes
static int countPalindromes(String S)
{
int N = (int)S.Length;
int[] Z = new int[(N)];
// Calculation of Z-array
int l = 0, r = 0;
for(int i = 1; i < N; i++)
{
if (i <= r)
Z[i] = Math.Min(r - i + 1,
Z[i - l]);
while (i + Z[i] < N &&
S[Z[i]] ==
S[i + Z[i]])
{
Z[i]++;
}
if (i + Z[i] - 1 > r)
{
l = i;
r = i + Z[i] - 1;
}
}
// Calculation of sigma(Z[i]+1)
int sum = 0;
for(int i = 0; i < Z.Length; i++)
{
sum += Z[i] + 1;
}
// Return the count
return sum;
}
// Driver Code
public static void Main(String[] args)
{
// Given String
String S = "abab";
Console.WriteLine(countPalindromes(S));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program the above approach
// Function to calculate the
// number of palindromes
function countPalindromes(S)
{
var N = S.length;
var Z = Array(N).fill(0);
// Calculation of Z-array
var l = 0, r = 0;
for (var i = 1; i < N; i++) {
if (i <= r)
Z[i] = Math.min(r - i + 1, Z[i - l]);
while (i + Z[i] < N
&& S[Z[i]] == S[i + Z[i]]) {
Z[i]++;
}
if (i + Z[i] - 1 > r) {
l = i;
r = i + Z[i] - 1;
}
}
// Calculation of sigma(Z[i]+1)
var sum = 0;
for (var i = 0; i < Z.length; i++) {
sum += Z[i] + 1;
}
// Return the count
return sum;
}
// Driver Code
// Given String
var S = "abab";
document.write( countPalindromes(S));
</script>
6
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por mukulbindal170299 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA