Dado un flujo de caracteres (los caracteres se reciben uno por uno), escriba una función que imprima ‘Sí’ si un carácter hace el palíndromo de string completo, de lo contrario imprima ‘No’.
Ejemplos:
Input: str[] = "abcba"
Output: a Yes // "a" is palindrome
b No // "ab" is not palindrome
c No // "abc" is not palindrome
b No // "abcb" is not palindrome
a Yes // "abcba" is palindrome
Input: str[] = "aabaacaabaa"
Output: a Yes // "a" is palindrome
a Yes // "aa" is palindrome
b No // "aab" is not palindrome
a No // "aaba" is not palindrome
a Yes // "aabaa" is palindrome
c No // "aabaac" is not palindrome
a No // "aabaaca" is not palindrome
a No // "aabaacaa" is not palindrome
b No // "aabaacaab" is not palindrome
a No // "aabaacaaba" is not palindrome
a Yes // "aabaacaabaa" is palindrome
Deje que la string de entrada sea str[0..n-1].
Una solución simple es hacer lo siguiente para cada carácter str[i] en la string de entrada. Compruebe si la substring str[0…i] es palíndromo, luego imprima sí, de lo contrario imprima no.
Una mejor solución es utilizar la idea de Rolling Hash utilizada en el algoritmo Rabin Karp . La idea es realizar un seguimiento del reverso de la primera mitad y la segunda mitad (también usamos la primera mitad y el reverso de la segunda mitad) para cada índice. A continuación se muestra el algoritmo completo.
1) The first character is always a palindrome, so print yes for
first character.
2) Initialize reverse of first half as "a" and second half as "b".
Let the hash value of first half reverse be 'firstr' and that of
second half be 'second'.
3) Iterate through string starting from second character, do following
for every character str[i], i.e., i varies from 1 to n-1.
a) If 'firstr' and 'second' are same, then character by character
check the substring ending with current character and print
"Yes" if palindrome.
Note that if hash values match, then strings need not be same.
For example, hash values of "ab" and "ba" are same, but strings
are different. That is why we check complete string after hash.
b) Update 'firstr' and 'second' for next iteration.
If 'i' is even, then add next character to the beginning of
'firstr' and end of second half and update
hash values.
If 'i' is odd, then keep 'firstr' as it is, remove leading
character from second and append a next
character at end.
Veamos todos los pasos por ejemplo
string “ abcba ” Valores iniciales de ‘primero’ y ‘segundo’
firstr’ = hash(“a”), ‘segunda’ = hash(“b”) Comienza desde el segundo carácter, es decir, i = 1
- Compare ‘primero’ y ‘segundo’, no coinciden, así que imprima no.
- Calcule los valores hash para la próxima iteración, es decir, i = 2
Dado que i es impar, ‘primero’ no cambia y ‘segundo’ se convierte en hash («c») i = 2
- Compare ‘primero’ y ‘segundo’, no coinciden, así que imprima no.
- Calcule los valores hash para la próxima iteración, es decir, i = 3
Dado que i es par, ‘primero’ se convierte en hash («ba») y ‘segundo’ se convierte en hash («cb») i = 3
- Compare ‘primero’ y ‘segundo’, no coinciden, así que imprima no.
- Calcule los valores hash para la próxima iteración, es decir, i = 4
Dado que i es impar, ‘primero’ no cambia y ‘segundo’ se convierte en hash («ba») i = 4
- ‘primero’ y ‘segundo’ coinciden, compare las strings completas, coinciden, así que imprima sí
- No necesitamos calcular los siguientes valores hash ya que este es el último índice. La idea de usar hashes rodantes es que el siguiente valor hash se puede calcular desde el anterior en tiempo O (1) simplemente haciendo un número constante de operaciones aritméticas. A continuación se muestran las implementaciones del enfoque anterior.
C
// C program for online algorithm for palindrome checking
#include<stdio.h>
#include<string.h>
// d is the number of characters in input alphabet
#define d 256
// q is a prime number used for evaluating Rabin Karp's Rolling hash
#define q 103
void checkPalindromes(char str[])
{
// Length of input string
int N = strlen(str);
// A single character is always a palindrome
printf("%c Yes\n", str[0]);
// Return if string has only one character
if (N == 1) return;
// Initialize first half reverse and second half for
// as firstr and second characters
int firstr = str[0] % q;
int second = str[1] % q;
int h = 1, i, j;
// Now check for palindromes from second character
// onward
for (i=1; i<N; i++)
{
// If the hash values of 'firstr' and 'second'
// match, then only check individual characters
if (firstr == second)
{
/* Check if str[0..i] is palindrome using
simple character by character match */
for (j = 0; j < i/2; j++)
{
if (str[j] != str[i-j])
break;
}
(j == i/2)? printf("%c Yes\n", str[i]):
printf("%c No\n", str[i]);
}
else printf("%c No\n", str[i]);
// Calculate hash values for next iteration.
// Don't calculate hash for next characters if
// this is the last character of string
if (i != N-1)
{
// If i is even (next i is odd)
if (i%2 == 0)
{
// Add next character after first half at beginning
// of 'firstr'
h = (h*d) % q;
firstr = (firstr + h*str[i/2])%q;
// Add next character after second half at the end
// of second half.
second = (second*d + str[i+1])%q;
}
else
{
// If next i is odd (next i is even) then we
// need not to change firstr, we need to remove
// first character of second and append a
// character to it.
second = (d*(second + q - str[(i+1)/2]*h)%q
+ str[i+1])%q;
}
}
}
}
/* Driver program to test above function */
int main()
{
char *txt = "aabaacaabaa";
checkPalindromes(txt);
getchar();
return 0;
}
Java
// Java program for online algorithm for
// palindrome checking
public class GFG
{
// d is the number of characters in
// input alphabet
static final int d = 256;
// q is a prime number used for
// evaluating Rabin Karp's Rolling hash
static final int q = 103;
static void checkPalindromes(String str)
{
// Length of input string
int N = str.length();
// A single character is always a palindrome
System.out.println(str.charAt(0)+" Yes");
// Return if string has only one character
if (N == 1) return;
// Initialize first half reverse and second
// half for as firstr and second characters
int firstr = str.charAt(0) % q;
int second = str.charAt(1) % q;
int h = 1, i, j;
// Now check for palindromes from second
// character onward
for (i = 1; i < N; i++)
{
// If the hash values of 'firstr' and
// 'second' match, then only check
// individual characters
if (firstr == second)
{
/* Check if str[0..i] is palindrome
using simple character by character
match */
for (j = 0; j < i/2; j++)
{
if (str.charAt(j) != str.charAt(i
- j))
break;
}
System.out.println((j == i/2) ?
str.charAt(i) + " Yes": str.charAt(i)+
" No");
}
else System.out.println(str.charAt(i)+ " No");
// Calculate hash values for next iteration.
// Don't calculate hash for next characters
// if this is the last character of string
if (i != N - 1)
{
// If i is even (next i is odd)
if (i % 2 == 0)
{
// Add next character after first
// half at beginning of 'firstr'
h = (h * d) % q;
firstr = (firstr + h *str.charAt(i /
2)) % q;
// Add next character after second
// half at the end of second half.
second = (second * d + str.charAt(i +
1)) % q;
}
else
{
// If next i is odd (next i is even)
// then we need not to change firstr,
// we need to remove first character
// of second and append a character
// to it.
second = (d * (second + q - str.charAt(
(i + 1) / 2) * h) % q +
str.charAt(i + 1)) % q;
}
}
}
}
/* Driver program to test above function */
public static void main(String args[])
{
String txt = "aabaacaabaa";
checkPalindromes(txt);
}
}
// This code is contributed by Sumit Ghosh
Python
# Python program Online algorithm for checking palindrome # in a stream # d is the number of characters in input alphabet d = 256 # q is a prime number used for evaluating Rabin Karp's # Rolling hash q = 103 def checkPalindromes(string): # Length of input string N = len(string) # A single character is always a palindrome print string[0] + " Yes" # Return if string has only one character if N == 1: return # Initialize first half reverse and second half for # as firstr and second characters firstr = ord(string[0]) % q second = ord(string[1]) % q h = 1 i = 0 j = 0 # Now check for palindromes from second character # onward for i in xrange(1,N): # If the hash values of 'firstr' and 'second' # match, then only check individual characters if firstr == second: # Check if str[0..i] is palindrome using # simple character by character match for j in xrange(0,i/2): if string[j] != string[i-j]: break j += 1 if j == i/2: print string[i] + " Yes" else: print string[i] + " No" else: print string[i] + " No" # Calculate hash values for next iteration. # Don't calculate hash for next characters if # this is the last character of string if i != N-1: # If i is even (next i is odd) if i % 2 == 0: # Add next character after first half at # beginning of 'firstr' h = (h*d) % q firstr = (firstr + h*ord(string[i/2]))%q # Add next character after second half at # the end of second half. second = (second*d + ord(string[i+1]))%q else: # If next i is odd (next i is even) then we # need not to change firstr, we need to remove # first character of second and append a # character to it. second = (d*(second + q - ord(string[(i+1)/2])*h)%q + ord(string[i+1]))%q # Driver program txt = "aabaacaabaa" checkPalindromes(txt) # This code is contributed by Bhavya Jain
C#
// C# program for online algorithm for
// palindrome checking
using System;
class GFG
{
// d is the number of characters
// in input alphabet
public const int d = 256;
// q is a prime number used for
// evaluating Rabin Karp's Rolling hash
public const int q = 103;
public static void checkPalindromes(string str)
{
// Length of input string
int N = str.Length;
// A single character is always
// a palindrome
Console.WriteLine(str[0] + " Yes");
// Return if string has only
// one character
if (N == 1)
{
return;
}
// Initialize first half reverse and second
// half for as firstr and second characters
int firstr = str[0] % q;
int second = str[1] % q;
int h = 1, i, j;
// Now check for palindromes from
// second character onward
for (i = 1; i < N; i++)
{
// If the hash values of 'firstr'
// and 'second' match, then only
// check individual characters
if (firstr == second)
{
/* Check if str[0..i] is palindrome
using simple character by character
match */
for (j = 0; j < i / 2; j++)
{
if (str[j] != str[i - j])
{
break;
}
}
Console.WriteLine((j == i / 2) ? str[i] +
" Yes": str[i] + " No");
}
else
{
Console.WriteLine(str[i] + " No");
}
// Calculate hash values for next iteration.
// Don't calculate hash for next characters
// if this is the last character of string
if (i != N - 1)
{
// If i is even (next i is odd)
if (i % 2 == 0)
{
// Add next character after first
// half at beginning of 'firstr'
h = (h * d) % q;
firstr = (firstr + h * str[i / 2]) % q;
// Add next character after second
// half at the end of second half.
second = (second * d + str[i + 1]) % q;
}
else
{
// If next i is odd (next i is even)
// then we need not to change firstr,
// we need to remove first character
// of second and append a character
// to it.
second = (d * (second + q - str[(i + 1) / 2] *
h) % q + str[i + 1]) % q;
}
}
}
}
// Driver Code
public static void Main(string[] args)
{
string txt = "aabaacaabaa";
checkPalindromes(txt);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript program to delete elements from array.
// Function for deleting k elements
function checkPalindromes(str)
{
// d is the number of characters in
// input alphabet
var d = 256;
// q is a prime number used for
// evaluating Rabin Karp's Rolling hash
var q = 103
var n = str.length;
document.write(str.charAt(0)+" Yes");
document.write("\n");
if(n==1)
{
return;
}
// Initialize first half reverse and second
// half for as firstr and second characters
var firstr = str.charAt(0) % q;
var second = str.charAt(1) % q;
var h = 1, i, j;
// Now check for palindromes from second
// character onward
for (var i = 1; i < n; i++)
{
// If the hash values of 'firstr' and
// 'second' match, then only check
// individual characters
if (firstr == second)
{
/* Check if str[0..i] is palindrome
using simple character by character
match */
for (j = 0; j < i/2; j++)
{
if (str.charAt(j) != str.charAt(i
- j))
break;
}
document.write((j == i/2) ?
str.charAt(i) + " Yes": str.charAt(i)+
" No");
document.write("\n");
}
else document.write(str.charAt(i)+ " No");
document.write("\n");
// Calculate hash values for next iteration.
// Don't calculate hash for next characters
// if this is the last character of string
if (i != n - 1)
{
// If i is even (next i is odd)
if (i % 2 == 0)
{
// Add next character after first
// half at beginning of 'firstr'
h = (h * d) % q;
firstr = (firstr + h *str.charAt(i /
2)) % q;
// Add next character after second
// half at the end of second half.
second = (second * d + str.charAt(i +
1)) % q;
}
else
{
// If next i is odd (next i is even)
// then we need not to change firstr,
// we need to remove first character
// of second and append a character
// to it.
second = (d * (second + q - str.charAt(
(i + 1) / 2) * h) % q +
str.charAt(i + 1)) % q;
}
}
}
}
// Driver code
var txt = "aabaacaabaa";
checkPalindromes(txt);
// This code is contributed by Aarti_Rathi
</script>
Producción
a Yes a Yes b No a No a Yes c No a No a No b No a No a Yes
La complejidad de tiempo del peor caso de la solución anterior sigue siendo O(n*n), pero en general, funciona mucho mejor que el enfoque simple, ya que evitamos la comparación completa de substrings la mayor parte del tiempo al comparar primero los valores hash.
El peor caso ocurre para strings de entrada con todos los mismos caracteres como «aaaaaa».
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