En Algoritmo de Manacher Parte 1 y Parte 2 , repasamos algunos de los conceptos básicos, entendimos la array de longitud LPS y cómo calcularla de manera eficiente en base a cuatro casos. Aquí implementaremos lo mismo.
Hemos visto que no se necesitan nuevas comparaciones de caracteres en el caso 1 y el caso 2. En los casos 3 y 4, se necesitan nuevas comparaciones necesarias.
En la siguiente figura,
Si necesitamos una comparación, solo compararemos los caracteres reales, que están en posiciones «impares» como 1, 3, 5, 7, etc.
Las posiciones pares no representan un carácter en la string, por lo que no se realizará ninguna comparación para incluso posiciones.
Si dos caracteres en diferentes posiciones impares coinciden, aumentarán la longitud de LPS en 2.
Hay muchas formas de implementar esto dependiendo de cómo se manejen las posiciones pares e impares. Una forma sería crear una nueva string primero donde insertamos algún carácter único (por ejemplo, #, $, etc.) en todas las posiciones pares y luego ejecutar el algoritmo en eso (para evitar diferentes formas de manejo de posiciones pares e impares). Otra forma podría ser trabajar en la string dada, pero aquí las posiciones pares e impares deben manejarse adecuadamente.
Aquí comenzaremos con la string dada en sí. Cuando haya una necesidad de expansión y se requiera una comparación de caracteres, expandiremos en las posiciones izquierda y derecha una por una. Cuando se encuentre una posición impar, se realizará una comparación y la longitud LPS se incrementará en UNO. Cuando se encuentra una posición par, no se realiza ninguna comparación y la longitud de LPS se incrementará en UNO (por lo tanto, en general, una posición impar y una par en los lados izquierdo y derecho aumentarán la longitud de LPS en DOS).
Implementación:
C
// A C program to implement Manacher’s Algorithm
#include <stdio.h>
#include <string.h>
char text[100];
void findLongestPalindromicString()
{
int N = strlen(text);
if(N == 0)
return;
N = 2*N + 1; //Position count
int L[N]; //LPS Length Array
L[0] = 0;
L[1] = 1;
int C = 1; //centerPosition
int R = 2; //centerRightPosition
int i = 0; //currentRightPosition
int iMirror; //currentLeftPosition
int expand = -1;
int diff = -1;
int maxLPSLength = 0;
int maxLPSCenterPosition = 0;
int start = -1;
int end = -1;
//Uncomment it to print LPS Length array
//printf("%d %d ", L[0], L[1]);
for (i = 2; i < N; i++)
{
//get currentLeftPosition iMirror for currentRightPosition i
iMirror = 2*C-i;
//Reset expand - means no expansion required
expand = 0;
diff = R - i;
//If currentRightPosition i is within centerRightPosition R
if(diff >= 0)
{
if(L[iMirror] < diff) // Case 1
L[i] = L[iMirror];
else if(L[iMirror] == diff && R == N-1) // Case 2
L[i] = L[iMirror];
else if(L[iMirror] == diff && R < N-1) // Case 3
{
L[i] = L[iMirror];
expand = 1; // expansion required
}
else if(L[iMirror] > diff) // Case 4
{
L[i] = diff;
expand = 1; // expansion required
}
}
else
{
L[i] = 0;
expand = 1; // expansion required
}
if (expand == 1)
{
//Attempt to expand palindrome centered at currentRightPosition i
//Here for odd positions, we compare characters and
//if match then increment LPS Length by ONE
//If even position, we just increment LPS by ONE without
//any character comparison
while (((i + L[i]) < N && (i - L[i]) > 0) &&
( ((i + L[i] + 1) % 2 == 0) ||
(text[(i + L[i] + 1)/2] == text[(i-L[i]-1)/2] )))
{
L[i]++;
}
}
if(L[i] > maxLPSLength) // Track maxLPSLength
{
maxLPSLength = L[i];
maxLPSCenterPosition = i;
}
// If palindrome centered at currentRightPosition i
// expand beyond centerRightPosition R,
// adjust centerPosition C based on expanded palindrome.
if (i + L[i] > R)
{
C = i;
R = i + L[i];
}
//Uncomment it to print LPS Length array
//printf("%d ", L[i]);
}
//printf("\n");
start = (maxLPSCenterPosition - maxLPSLength)/2;
end = start + maxLPSLength - 1;
//printf("start: %d end: %d\n", start, end);
printf("LPS of string is %s : ", text);
for(i=start; i<=end; i++)
printf("%c", text[i]);
printf("\n");
}
int main(int argc, char *argv[])
{
strcpy(text, "babcbabcbaccba");
findLongestPalindromicString();
strcpy(text, "abaaba");
findLongestPalindromicString();
strcpy(text, "abababa");
findLongestPalindromicString();
strcpy(text, "abcbabcbabcba");
findLongestPalindromicString();
strcpy(text, "forgeeksskeegfor");
findLongestPalindromicString();
strcpy(text, "caba");
findLongestPalindromicString();
strcpy(text, "abacdfgdcaba");
findLongestPalindromicString();
strcpy(text, "abacdfgdcabba");
findLongestPalindromicString();
strcpy(text, "abacdedcaba");
findLongestPalindromicString();
return 0;
}
Java
// A Java program to implement Manacher’s Algorithm
import java.lang.*;
class GFG{
public static void findLongestPalindromicString(
String text)
{
int N = text.length();
if(N == 0)
return;
// Position count
N = 2 * N + 1;
// LPS Length Array
int []L = new int [N];
L[0] = 0;
L[1] = 1;
// centerPosition
int C = 1;
// centerRightPosition
int R = 2;
// currentRightPosition
int i = 0;
// currentLeftPosition
int iMirror;
int expand = -1;
int diff = -1;
int maxLPSLength = 0;
int maxLPSCenterPosition = 0;
int start = -1;
int end = -1;
// Uncomment it to print LPS Length array
// printf("%d %d ", L[0], L[1]);
for (i = 2; i < N; i++)
{
// Get currentLeftPosition iMirror
// for currentRightPosition i
iMirror = 2 * C - i;
// Reset expand - means no
// expansion required
expand = 0;
diff = R - i;
// If currentRightPosition i is
// within centerRightPosition R
if(diff >= 0)
{
// Case 1
if(L[iMirror] < diff)
L[i] = L[iMirror];
// Case 2
else if(L[iMirror] == diff && R == N - 1)
L[i] = L[iMirror];
// Case 3
else if(L[iMirror] == diff && R < N - 1)
{
L[i] = L[iMirror];
// Expansion required
expand = 1;
}
// Case 4
else if(L[iMirror] > diff)
{
L[i] = diff;
// Expansion required
expand = 1;
}
}
else
{
L[i] = 0;
// Expansion required
expand = 1;
}
if (expand == 1)
{
// Attempt to expand palindrome centered
// at currentRightPosition i. Here for odd
// positions, we compare characters and
// if match then increment LPS Length by ONE
// If even position, we just increment LPS
// by ONE without any character comparison
try
{
while (((i + L[i]) < N &&
(i - L[i]) > 0) &&
(((i + L[i] + 1) % 2 == 0) ||
(text.charAt((i + L[i] + 1) / 2) ==
text.charAt((i - L[i] - 1) / 2))))
{
L[i]++;
}
}
catch (Exception e)
{
assert true;
}
}
// Track maxLPSLength
if(L[i] > maxLPSLength)
{
maxLPSLength = L[i];
maxLPSCenterPosition = i;
}
// If palindrome centered at
// currentRightPosition i expand
// beyond centerRightPosition R,
// adjust centerPosition C based
// on expanded palindrome.
if (i + L[i] > R)
{
C = i;
R = i + L[i];
}
//Uncomment it to print LPS Length array
//System.out.print("%d ", L[i]);
}
start = (maxLPSCenterPosition -
maxLPSLength) / 2;
end = start + maxLPSLength - 1;
//System.out.print("start: %d end: %d\n",
// start, end);
System.out.print("LPS of string is " +
text + " : ");
for(i = start; i <= end; i++)
System.out.print(text.charAt(i));
System.out.println();
}
// Driver code
public static void main(String []args)
{
String text1="babcbabcbaccba";
findLongestPalindromicString(text1);
String text2="abaaba";
findLongestPalindromicString(text2);
String text3= "abababa";
findLongestPalindromicString(text3);
String text4="abcbabcbabcba";
findLongestPalindromicString(text4);
String text5="forgeeksskeegfor";
findLongestPalindromicString(text5);
String text6="caba";
findLongestPalindromicString(text6);
String text7="abacdfgdcaba";
findLongestPalindromicString(text7);
String text8="abacdfgdcabba";
findLongestPalindromicString(text8);
String text9="abacdedcaba";
findLongestPalindromicString(text9);
}
}
// This code is contributed by SoumikMondal
Python3
# Python program to implement Manacher's Algorithm
def findLongestPalindromicString(text):
N = len(text)
if N == 0:
return
N = 2*N+1 # Position count
L = [0] * N
L[0] = 0
L[1] = 1
C = 1 # centerPosition
R = 2 # centerRightPosition
i = 0 # currentRightPosition
iMirror = 0 # currentLeftPosition
maxLPSLength = 0
maxLPSCenterPosition = 0
start = -1
end = -1
diff = -1
# Uncomment it to print LPS Length array
# printf("%d %d ", L[0], L[1]);
for i in range(2,N):
# get currentLeftPosition iMirror for currentRightPosition i
iMirror = 2*C-i
L[i] = 0
diff = R - i
# If currentRightPosition i is within centerRightPosition R
if diff > 0:
L[i] = min(L[iMirror], diff)
# Attempt to expand palindrome centered at currentRightPosition i
# Here for odd positions, we compare characters and
# if match then increment LPS Length by ONE
# If even position, we just increment LPS by ONE without
# any character comparison
try:
while ((i+L[i]) < N and (i-L[i]) > 0) and \
(((i+L[i]+1) % 2 == 0) or \
(text[(i+L[i]+1)//2] == text[(i-L[i]-1)//2])):
L[i]+=1
except Exception as e:
pass
if L[i] > maxLPSLength: # Track maxLPSLength
maxLPSLength = L[i]
maxLPSCenterPosition = i
# If palindrome centered at currentRightPosition i
# expand beyond centerRightPosition R,
# adjust centerPosition C based on expanded palindrome.
if i + L[i] > R:
C = i
R = i + L[i]
# Uncomment it to print LPS Length array
# printf("%d ", L[i]);
start = (maxLPSCenterPosition - maxLPSLength) // 2
end = start + maxLPSLength - 1
print ("LPS of string is " + text + " : ",text[start:end+1])
# Driver program
text1 = "babcbabcbaccba"
findLongestPalindromicString(text1)
text2 = "abaaba"
findLongestPalindromicString(text2)
text3 = "abababa"
findLongestPalindromicString(text3)
text4 = "abcbabcbabcba"
findLongestPalindromicString(text4)
text5 = "forgeeksskeegfor"
findLongestPalindromicString(text5)
text6 = "caba"
findLongestPalindromicString(text6)
text7 = "abacdfgdcaba"
findLongestPalindromicString(text7)
text8 = "abacdfgdcabba"
findLongestPalindromicString(text8)
text9 = "abacdedcaba"
findLongestPalindromicString(text9)
# This code is contributed by BHAVYA JAIN
C#
// A C# program to implement Manacher’s Algorithm
using System;
using System.Diagnostics;
public class GFG
{
public static void findLongestPalindromicString(
String text)
{
int N = text.Length;
if(N == 0)
return;
// Position count
N = 2 * N + 1;
// LPS Length Array
int []L = new int [N];
L[0] = 0;
L[1] = 1;
// centerPosition
int C = 1;
// centerRightPosition
int R = 2;
// currentRightPosition
int i = 0;
// currentLeftPosition
int iMirror;
int expand = -1;
int diff = -1;
int maxLPSLength = 0;
int maxLPSCenterPosition = 0;
int start = -1;
int end = -1;
// Uncomment it to print LPS Length array
// printf("%d %d ", L[0], L[1]);
for (i = 2; i < N; i++)
{
// Get currentLeftPosition iMirror
// for currentRightPosition i
iMirror = 2 * C - i;
// Reset expand - means no
// expansion required
expand = 0;
diff = R - i;
// If currentRightPosition i is
// within centerRightPosition R
if(diff >= 0)
{
// Case 1
if(L[iMirror] < diff)
L[i] = L[iMirror];
// Case 2
else if(L[iMirror] == diff && R == N - 1)
L[i] = L[iMirror];
// Case 3
else if(L[iMirror] == diff && R < N - 1)
{
L[i] = L[iMirror];
// Expansion required
expand = 1;
}
// Case 4
else if(L[iMirror] > diff)
{
L[i] = diff;
// Expansion required
expand = 1;
}
}
else
{
L[i] = 0;
// Expansion required
expand = 1;
}
if (expand == 1)
{
// Attempt to expand palindrome centered
// at currentRightPosition i. Here for odd
// positions, we compare characters and
// if match then increment LPS Length by ONE
// If even position, we just increment LPS
// by ONE without any character comparison
try
{
while (((i + L[i]) < N &&
(i - L[i]) > 0) &&
(((i + L[i] + 1) % 2 == 0) ||
(text[(i + L[i] + 1) / 2] ==
text[(i - L[i] - 1) / 2])))
{
L[i]++;
}
}
catch (Exception)
{
Debug.Assert(true);
}
}
// Track maxLPSLength
if(L[i] > maxLPSLength)
{
maxLPSLength = L[i];
maxLPSCenterPosition = i;
}
// If palindrome centered at
// currentRightPosition i expand
// beyond centerRightPosition R,
// adjust centerPosition C based
// on expanded palindrome.
if (i + L[i] > R)
{
C = i;
R = i + L[i];
}
//Uncomment it to print LPS Length array
//System.out.print("%d ", L[i]);
}
start = (maxLPSCenterPosition -
maxLPSLength) / 2;
end = start + maxLPSLength - 1;
//System.out.print("start: %d end: %d\n",
// start, end);
Console.Write("LPS of string is " +
text + " : ");
for(i = start; i <= end; i++)
Console.Write(text[i]);
Console.WriteLine();
}
// Driver code
static public void Main ()
{
String text1 = "babcbabcbaccba";
findLongestPalindromicString(text1);
String text2 = "abaaba";
findLongestPalindromicString(text2);
String text3 = "abababa";
findLongestPalindromicString(text3);
String text4 = "abcbabcbabcba";
findLongestPalindromicString(text4);
String text5 = "forgeeksskeegfor";
findLongestPalindromicString(text5);
String text6 = "caba";
findLongestPalindromicString(text6);
String text7 = "abacdfgdcaba";
findLongestPalindromicString(text7);
String text8 = "abacdfgdcabba";
findLongestPalindromicString(text8);
String text9 = "abacdedcaba";
findLongestPalindromicString(text9);
}
}
// This code is contributed by Dharanendra L V.
Javascript
<script>
// A Javascript program to implement Manacher’s Algorithm
function findLongestPalindromicString(text)
{
let N = text.length;
if(N == 0)
return;
// Position count
N = 2 * N + 1;
// LPS Length Array
let L = new Array(N);
L[0] = 0;
L[1] = 1;
// centerPosition
let C = 1;
// centerRightPosition
let R = 2;
// currentRightPosition
let i = 0;
// currentLeftPosition
let iMirror;
let expand = -1;
let diff = -1;
let maxLPSLength = 0;
let maxLPSCenterPosition = 0;
let start = -1;
let end = -1;
// Uncomment it to print LPS Length array
// printf("%d %d ", L[0], L[1]);
for (i = 2; i < N; i++)
{
// Get currentLeftPosition iMirror
// for currentRightPosition i
iMirror = 2 * C - i;
// Reset expand - means no
// expansion required
expand = 0;
diff = R - i;
// If currentRightPosition i is
// within centerRightPosition R
if(diff >= 0)
{
// Case 1
if(L[iMirror] < diff)
L[i] = L[iMirror];
// Case 2
else if(L[iMirror] == diff && R == N - 1)
L[i] = L[iMirror];
// Case 3
else if(L[iMirror] == diff && R < N - 1)
{
L[i] = L[iMirror];
// Expansion required
expand = 1;
}
// Case 4
else if(L[iMirror] > diff)
{
L[i] = diff;
// Expansion required
expand = 1;
}
}
else
{
L[i] = 0;
// Expansion required
expand = 1;
}
if (expand == 1)
{
// Attempt to expand palindrome centered
// at currentRightPosition i. Here for odd
// positions, we compare characters and
// if match then increment LPS Length by ONE
// If even position, we just increment LPS
// by ONE without any character comparison
while (((i + L[i]) < N &&
(i - L[i]) > 0) &&
(((i + L[i] + 1) % 2 == 0) ||
(text[Math.floor((i + L[i] + 1) / 2)] ==
text[Math.floor((i - L[i] - 1) / 2)])))
{
L[i]++;
}
}
// Track maxLPSLength
if(L[i] > maxLPSLength)
{
maxLPSLength = L[i];
maxLPSCenterPosition = i;
}
// If palindrome centered at
// currentRightPosition i expand
// beyond centerRightPosition R,
// adjust centerPosition C based
// on expanded palindrome.
if (i + L[i] > R)
{
C = i;
R = i + L[i];
}
//Uncomment it to print LPS Length array
//System.out.print("%d ", L[i]);
}
start = (maxLPSCenterPosition -
maxLPSLength) / 2;
end = start + maxLPSLength - 1;
//System.out.print("start: %d end: %d\n",
// start, end);
document.write("LPS of string is " +
text + " : ");
for(i = start; i <= end; i++)
document.write(text[i]);
document.write("<br>");
}
// Driver code
let text1="babcbabcbaccba";
findLongestPalindromicString(text1);
let text2="abaaba";
findLongestPalindromicString(text2);
let text3= "abababa";
findLongestPalindromicString(text3);
let text4="abcbabcbabcba";
findLongestPalindromicString(text4);
let text5="forgeeksskeegfor";
findLongestPalindromicString(text5);
let text6="caba";
findLongestPalindromicString(text6);
let text7="abacdfgdcaba";
findLongestPalindromicString(text7);
let text8="abacdfgdcabba";
findLongestPalindromicString(text8);
let text9="abacdedcaba";
findLongestPalindromicString(text9);
// This code is contributed by unknown2108
</script>
Producción
LPS of string is babcbabcbaccba : abcbabcba LPS of string is abaaba : abaaba LPS of string is abababa : abababa LPS of string is abcbabcbabcba : abcbabcbabcba LPS of string is forgeeksskeegfor : geeksskeeg LPS of string is caba : aba LPS of string is abacdfgdcaba : aba LPS of string is abacdfgdcabba : abba LPS of string is abacdedcaba : abacdedcaba
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Esta es la implementación basada en los cuatro casos discutidos en la Parte 2 . En la Parte 4 , hemos discutido una forma diferente de ver estos cuatro casos y algunos otros enfoques.
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