Dada una string s de longitud n, cuente el número de substrings que tienen diferentes tipos de características palindrómicas.
La característica palindrómica es el número de k-palíndromos en una string donde k se encuentra en el rango [0, n).
Una string es 1-palíndromo (o simplemente palíndromo) si y solo si se lee igual hacia atrás que hacia adelante.
Una cuerda es k-palíndromo (k > 1) si y sólo si:
1. Su mitad izquierda es igual a su mitad derecha.
2. Su mitad izquierda y mitad derecha deben ser palíndromos no vacíos (k – 1). La mitad izquierda de una string de longitud ‘t’ es su prefijo de longitud ⌊t/2⌋, y la mitad derecha es el sufijo de la misma longitud.
Nota:Cada substring se cuenta tantas veces como aparece en la string. Por ejemplo, en la string “aaa” la substring “a” aparece 3 veces.
Ejemplos:
Input : abba Output : 6 1 0 0 Explanation : "6" 1-palindromes = "a", "b", "b", "a", "bb", "abba". "1" 2-palindrome = "bb". Because "b" is 1-palindrome and "bb" has both left and right parts equal. "0" 3-palindrome and 4-palindrome. Input : abacaba Output : 12 4 1 0 0 0 0 Explanation : "12" 1-palindromes = "a", "b", "a", "c", "a", "b", "a", "aba", "aca", "aba", "bacab", "abacaba". "4" 2-palindromes = "aba", "aca", "aba", "abacaba". Because "a" and "aba" are 1-palindromes. NOTE : "bacab" is not 2-palindrome as "ba" is not 1-palindrome. "1" 3-palindrome = "abacaba". Because is "aba" is 2-palindrome. "0" other k-palindromes where 4 < = k < = 7.
Enfoque: tome una string s y diga que es un palíndromo de 1 y verifique que su mitad izquierda también resulte ser un palíndromo de 1 entonces, obviamente, su parte derecha siempre será igual a la parte izquierda (ya que la string también es un palíndromo de 1 -palindrome) haciendo que la string original sea 2-palindrome. Ahora, de manera similar, al verificar la mitad izquierda de la string, también resulta ser un palíndromo 1, luego hará que la mitad izquierda sea un palíndromo 2 y, por lo tanto, hará que la string original sea un palíndromo 3 y así sucesivamente. hasta que solo quede 1 alfabeto o la parte no sea un 1-palíndromo.
Tomemos string = “abacaba”. Como se conoce “abacaba” es 1-palíndromo. Entonces, al verificar su mitad izquierda «aba», que también es un palíndromo de 1, convierte a «abacaba» en un palíndromo de 2. Luego, verifique la mitad izquierda «a» de «aba», que también es un palíndromo de 1. Entonces hace que «aba» sea un palíndromo de 2 y «aba» haga que «abacaba» sea un palíndromo de 3. Entonces, en otras palabras, si una string es un k-palíndromo, entonces también es un (k-1)-palíndromo, (k-2)-palíndromo, y así sucesivamente hasta 1-palíndromo. El código para el mismo se proporciona a continuación, que primero verifica todas y cada una de las substrings si es un palíndromo o no y luego cuenta el número de substrings k-palindrómicas recursivamente en tiempo logarítmico.
A continuación se muestra la implementación del enfoque anterior:
C++
// A C++ program which counts different
// palindromic characteristics of a string.
#include <bits/stdc++.h>
using namespace std;
const int MAX_STR_LEN = 1000;
bool P[MAX_STR_LEN][MAX_STR_LEN];
int Kpal[MAX_STR_LEN];
// A C++ function which checks whether a
// substring str[i..j] of a given string
// is a palindrome or not.
void checkSubStrPal(string str, int n)
{
// P[i][j] = true if substring str
// [i..j] is palindrome, else false
memset(P, false, sizeof(P));
// 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;
// Palindromes of length more then 2.
// This loop is similar to Matrix Chain
// Multiplication. We start with a gap of
// length 2 and fill P 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;
}
}
}
// A C++ function which recursively
// counts if a string str [i..j] is
// a k-palindromic string or not.
void countKPalindromes(int i, int j, int k)
{
// terminating condition for a
// string which is a k-palindrome.
if (i == j)
{
Kpal[k]++;
return;
}
// terminating condition for a
// string which is not a k-palindrome.
if (P[i][j] == false)
return;
// increases the counter for the
// string if it is a k-palindrome.
Kpal[k]++;
// mid is middle pointer of
// the string str [i...j].
int mid = (i + j) / 2;
// if length of string which is
// (j - i + 1) is odd than we have
// to subtract one from mid.
// else if even then no change.
if ((j - i + 1) % 2 == 1)
mid--;
// if the string is k-palindrome
// then we check if it is a
// (k+1) - palindrome or not by
// just sending any of one half of
// the string to the Count_k_Palindrome
// function.
countKPalindromes(i, mid, k + 1);
}
void printKPalindromes(string s)
{
// Count of k-palindromes is equal
// to zero initially.
memset(Kpal, 0, sizeof(Kpal));
// Finding all palindromic
// substrings of given string
int n = s.length();
checkSubStrPal(s, n);
// counting k-palindromes for each and
// every substring of given string. .
for (int i = 0; i < n; i++)
for (int j = 0; j < n - i; j++)
countKPalindromes(j, j + i, 1);
// Output the number of K-palindromic
// substrings of a given string.
for (int i = 1; i <= n; i++)
cout << Kpal[i] << " ";
cout << "\n";
}
// Driver code
int main()
{
string s = "abacaba";
printKPalindromes(s);
return 0;
}
Java
// Java program which counts
// different palindromic
// characteristics of a string.
import java.io.*;
class GFG
{
static int MAX_STR_LEN = 1000;
static boolean P[][] =
new boolean[MAX_STR_LEN][MAX_STR_LEN];
static int []Kpal =
new int[MAX_STR_LEN];
// function which checks
// whether a substring
// str[i..j] of a given
// string is a palindrome or not.
static void checkSubStrPal(String str,
int n)
{
// P[i,j] = true if substring
// str [i..j] is palindrome,
// else false
for (int i = 0; i < MAX_STR_LEN; i++)
{
for (int j = 0; j < MAX_STR_LEN; j++)
P[i][j] = false;
Kpal[i] = 0;
}
// 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.charAt(i) == str.charAt(i + 1))
P[i][i + 1] = true;
// Palindromes of length
// more then 2. This loop
// is similar to Matrix
// Chain Multiplication.
// We start with a gap of
// length 2 and fill P 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.charAt(i) == str.charAt(j) &&
P[i + 1][j - 1])
P[i][j] = true;
}
}
}
// A function which recursively
// counts if a string str [i..j] is
// a k-palindromic string or not.
static void countKPalindromes(int i, int j,
int k)
{
// terminating condition
// for a string which is
// a k-palindrome.
if (i == j)
{
Kpal[k]++;
return;
}
// terminating condition for
// a string which is not a
// k-palindrome.
if (P[i][j] == false)
return;
// increases the counter
// for the string if it
// is a k-palindrome.
Kpal[k]++;
// mid is middle pointer of
// the string str [i...j].
int mid = (i + j) / 2;
// if length of string which
// is (j - i + 1) is odd than
// we have to subtract one
// from mid else if even then
// no change.
if ((j - i + 1) % 2 == 1)
mid--;
// if the string is k-palindrome
// then we check if it is a
// (k+1) - palindrome or not
// by just sending any of one
// half of the string to the
// Count_k_Palindrome function.
countKPalindromes(i, mid, k + 1);
}
static void printKPalindromes(String s)
{
// Finding all palindromic
// substrings of given string
int n = s.length();
checkSubStrPal(s, n);
// counting k-palindromes for
// each and every substring
// of given string. .
for (int i = 0; i < n; i++)
for (int j = 0; j < n - i; j++)
countKPalindromes(j, j + i, 1);
// Output the number of
// K-palindromic substrings
// of a given string.
for (int i = 1; i <= n; i++)
System.out.print(Kpal[i] + " ");
System.out.println();
}
// Driver code
public static void main(String args[])
{
String s = "abacaba";
printKPalindromes(s);
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
Python3
# Python program which counts # different palindromic # characteristics of a string. MAX_STR_LEN = 1000; P = [[0 for x in range(MAX_STR_LEN)] for y in range(MAX_STR_LEN)] ; for i in range(0, MAX_STR_LEN) : for j in range(0, MAX_STR_LEN) : P[i][j] = False; Kpal = [0] * MAX_STR_LEN; # def which checks # whether a substr[i..j] # of a given is a # palindrome or not. def checkSubStrPal(str, n) : global P, Kpal, MAX_STR_LEN; # P[i,j] = True if substr # [i..j] is palindrome, # else False for i in range(0, MAX_STR_LEN) : for j in range(0, MAX_STR_LEN) : P[i][j] = False; Kpal[i] = 0; # palindrome of # single length for i in range(0, n) : P[i][i] = True; # palindrome of # length 2 for i in range(0, n - 1) : if (str[i] == str[i + 1]) : P[i][i + 1] = True; # Palindromes of length more # then 2. This loop is similar # to Matrix Chain Multiplication. # We start with a gap of length # 2 and fill P table in a way # that gap between starting and # ending indexes increases one # by one by outer loop. for gap in range(2, n) : # Pick starting point # for current gap for i in range(0, 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; # A Python def which # recursively counts if # a str [i..j] is a # k-palindromic or not. def countKPalindromes(i, j, k) : global Kpal, P; # terminating condition # for a which is a # k-palindrome. if (i == j) : Kpal[k] = Kpal[k] + 1; return; # terminating condition # for a which is not a # k-palindrome. if (P[i][j] == False) : return; # increases the counter # for the if it is a # k-palindrome. Kpal[k] = Kpal[k] + 1; # mid is middle pointer # of the str [i...j]. mid = int((i + j) / 2); # if length of which is # (j - i + 1) is odd than # we have to subtract one # from mid else if even # then no change. if ((j - i + 1) % 2 == 1) : mid = mid - 1; # if the is k-palindrome # then we check if it is a # (k+1) - palindrome or not # by just sending any of # one half of the to the # Count_k_Palindrome def. countKPalindromes(i, mid, k + 1); def printKPalindromes(s) : global P, Kpal, MAX_STR_LEN; # Finding all palindromic # substrings of given string n = len(s); checkSubStrPal(s, n); # counting k-palindromes # for each and every sub # of given string. . for i in range(0, n) : for j in range(0, n - i) : countKPalindromes(j, j + i, 1); # Output the number of # K-palindromic substrings # of a given string. for i in range(1, n + 1) : print (Kpal[i], end=" "); print(); # Driver code s = "abacaba"; printKPalindromes(s); # This code is contributed by # Manish Shaw(manishshaw1)
C#
// C# program which counts
// different palindromic
// characteristics of a string.
using System;
class GFG
{
static int MAX_STR_LEN = 1000;
static bool [,]P = new bool[MAX_STR_LEN,
MAX_STR_LEN];
static int []Kpal = new int[MAX_STR_LEN];
// function which checks whether
// a substring str[i..j] of a
// given string is a palindrome or not.
static void checkSubStrPal(string str,
int n)
{
// P[i,j] = true if substring str
// [i..j] is palindrome, else false
for (int i = 0; i < MAX_STR_LEN; i++)
{
for (int j = 0; j < MAX_STR_LEN; j++)
P[i, j] = false;
Kpal[i] = 0;
}
// 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;
// Palindromes of length more
// then 2. This loop is similar
// to Matrix Chain Multiplication.
// We start with a gap of length 2
// and fill P 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;
}
}
}
// A C++ function which recursively
// counts if a string str [i..j] is
// a k-palindromic string or not.
static void countKPalindromes(int i, int j,
int k)
{
// terminating condition for a
// string which is a k-palindrome.
if (i == j)
{
Kpal[k]++;
return;
}
// terminating condition for
// a string which is not a
// k-palindrome.
if (P[i, j] == false)
return;
// increases the counter for the
// string if it is a k-palindrome.
Kpal[k]++;
// mid is middle pointer of
// the string str [i...j].
int mid = (i + j) / 2;
// if length of string which is
// (j - i + 1) is odd than we have
// to subtract one from mid.
// else if even then no change.
if ((j - i + 1) % 2 == 1)
mid--;
// if the string is k-palindrome
// then we check if it is a
// (k+1) - palindrome or not
// by just sending any of one
// half of the string to the
// Count_k_Palindrome function.
countKPalindromes(i, mid, k + 1);
}
static void printKPalindromes(string s)
{
// Finding all palindromic
// substrings of given string
int n = s.Length;
checkSubStrPal(s, n);
// counting k-palindromes for each and
// every substring of given string. .
for (int i = 0; i < n; i++)
for (int j = 0; j < n - i; j++)
countKPalindromes(j, j + i, 1);
// Output the number of K-palindromic
// substrings of a given string.
for (int i = 1; i <= n; i++)
Console.Write(Kpal[i] + " ");
Console.WriteLine();
}
// Driver code
static void Main()
{
string s = "abacaba";
printKPalindromes(s);
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
PHP
<?php
// PHP program which counts
// different palindromic
// characteristics of a string.
$MAX_STR_LEN = 1000;
$P = array(array());
$Kpal = array_fill(0, $MAX_STR_LEN, 0);
for($i = 0; $i < $MAX_STR_LEN; $i++)
{
for($j = 0; $j < $MAX_STR_LEN; $j++)
$P[$i][$j] = false;
}
// function which checks
// whether a substr[i..j]
// of a given is a
// palindrome or not.
function checkSubStrPal($str,
$n)
{
global $P, $Kpal,
$MAX_STR_LEN;
// P[i,j] = true if substr
// [i..j] is palindrome, else false
for ($i = 0;
$i < $MAX_STR_LEN; $i++)
{
for ($j = 0;
$j < $MAX_STR_LEN; $j++)
$P[$i][$j] = false;
$Kpal[$i] = 0;
}
// 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;
// Palindromes of length more
// then 2. This loop is similar
// to Matrix Chain Multiplication.
// We start with a gap of length
// 2 and fill P 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;
}
}
}
// A PHP function which
// recursively counts if
// a str [i..j] is a
// k-palindromic or not.
function countKPalindromes($i, $j, $k)
{
global $Kpal, $P;
// terminating condition for a
// which is a k-palindrome.
if ($i == $j)
{
$Kpal[$k]++;
return;
}
// terminating condition
// for a which is not a
// k-palindrome.
if ($P[$i][$j] == false)
return;
// increases the counter
// for the if it is a
// k-palindrome.
$Kpal[$k]++;
// mid is middle pointer
// of the str [i...j].
$mid = ($i + $j) / 2;
// if length of which is
// (j - i + 1) is odd than
// we have to subtract one
// from mid else if even
// then no change.
if (($j - $i + 1) % 2 == 1)
$mid--;
// if the is k-palindrome
// then we check if it is a
// (k+1) - palindrome or not
// by just sending any of
// one half of the to the
// Count_k_Palindrome function.
countKPalindromes($i, $mid,
$k + 1);
}
function printKPalindromes($s)
{
global $P, $Kpal,
$MAX_STR_LEN;
// Finding all palindromic
// substrings of given string
$n = strlen($s);
checkSubStrPal($s, $n);
// counting k-palindromes
// for each and every sub
// of given string. .
for ($i = 0; $i < $n; $i++)
for ($j = 0; $j < $n - $i; $j++)
countKPalindromes($j, $j +
$i, 1);
// Output the number of
// K-palindromic substrings
// of a given string.
for ($i = 1; $i <= $n; $i++)
echo ($Kpal[$i] . " ");
echo("\n");
}
// Driver code
$s = "abacaba";
printKPalindromes($s);
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Producción :
12 4 1 0 0 0 0
Complejidad de Tiempo : O( 
)
Espacio Auxiliar : O( 
)
Publicación traducida automáticamente
Artículo escrito por pulkitjain_NSIT y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA