algorithm - Algoritmo de Manacher(algoritmo para encontrar la subcadena palindrómica más larga en tiempo lineal)
palindrome (8)
Después de pasar unas 6-8 horas tratando de digerir el algoritmo del Manacher, estoy listo para tirar la toalla. Pero antes de hacerlo, aquí hay un último disparo en la oscuridad: ¿alguien puede explicarlo? No me importa el código. Quiero que alguien me explique el ALGORITMO .
Aquí parece haber un lugar que otros parecían disfrutar al explicar el algoritmo: http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
Entiendo por qué querrías transformar la cadena, por ejemplo, ''abba'' en # a # b # b # a # Después de lo que estoy perdido. Por ejemplo, el autor del sitio web mencionado anteriormente dice que la parte clave del algoritmo es:
if P[ i'' ] ≤ R – i,
then P[ i ] ← P[ i'' ]
else P[ i ] ≥ P[ i'' ]. (Which we have to expand past
the right edge (R) to find P[ i ])
Esto parece incorrecto, porque él / ella dice en un momento que P [i] es igual a 5 cuando P [i ''] = 7 y P [i] no es menor o igual a R - i.
Si no está familiarizado con el algoritmo, aquí hay algunos enlaces más: http://tristan-interview.blogspot.com/2011/11/longest-palindrome-substring-manachers.html (He probado este, pero el la terminología es horrible y confusa. Primero, algunas cosas no están definidas. Además, hay demasiadas variables. Necesita una lista de verificación para recordar qué variable se refiere a qué).
Otra es: http://www.akalin.cx/longest-palindrome-linear-time (buena suerte)
La esencia básica del algoritmo es encontrar el palíndromo más largo en tiempo lineal. Se puede hacer en O (n ^ 2) con una cantidad de esfuerzo de mínima a media. Se supone que este algoritmo es bastante "inteligente" para bajarlo a O (n).
Artículo completo: http://www.zrzahid.com/longest-palindromic-substring-in-linear-time-manachers-algorithm/
Antes que nada, observemos de cerca un palíndromo para encontrar algunas propiedades interesantes. Por ejemplo, S1 = "abaaba" y S2 = "abcba", ambos son palíndromos, pero ¿cuál es la diferencia no trivial (es decir, sin longitud ni caracteres) entre ellos? S1 es un palíndromo centrado alrededor del espacio invisible entre i = 2 e i = 3 (¡espacio inexistente!). Por otro lado, S2 se centra alrededor del carácter en i = 2 (es decir, c). Para manejar gentilmente el centro de un palíndromo, independientemente de la longitud impar / par, permite transformar el palíndromo insertando caracteres especiales $ entre los caracteres. Entonces S1 = "abba" y S2 = "abcba" se transformarán en T1 = "$ a $ b $ a $ a $ b $ a $" centrado en i = 6 y T2 = "$ a $ b $ c $ b $ a $ "centrado en i = 5. Ahora, podemos ver que los centros son existentes y las longitudes son consistentes 2 * n + 1, donde n = longitud de la cadena original. Por ejemplo,
i'' c i ----------------------------------------------------- | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| ----------------------------------------------------- T1=| $ | a | $ | b | $ | a | $ | a | $ | b | $ | a | $ | -----------------------------------------------------
A continuación, observe que a partir de la propiedad simétrica de un palíndromo T (transformado) alrededor del centro c, T [ck] = T [c + k] para 0 <= k <= c. Es decir, las posiciones ck y c + k son espejo el uno del otro. Digámoslo de otra manera, para un índice i a la derecha del centro c, el índice espejo i ''está a la izquierda de c tal que c-i'' = ic => i ''= 2 * ci y viceversa. Es decir,
Para cada posición i a la derecha del centro c de una subcadena palindrómica, la posición del espejo de i es, i ''= 2 * ci, y viceversa.
Definamos una matriz P [0..2 * n] tal que P [i] sea igual a la longitud del palíndromo centrado en i. Tenga en cuenta que, en realidad, la longitud se mide por el número de caracteres en la cadena original (ignorando caracteres especiales $). También, permita que min y max sean respectivamente el límite más a la izquierda y más a la derecha de una subcadena palindrómica centrada en c. Entonces, min = cP [c] y max = c + P [c]. Por ejemplo, para el palíndromo S = "abaaba", el palíndromo transformado T, el centro del espejo c = 6, la matriz de longitud P [0..12], min = cP [c] = 6-6 = 0, max = c + P [c] = 6 + 6 = 12 y dos índices reflejados de muestra i e i ''se muestran en la siguiente figura.
min i'' c i max ----------------------------------------------------- | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| ----------------------------------------------------- T=| $ | a | $ | b | $ | a | $ | a | $ | b | $ | a | $ | ----------------------------------------------------- P=| 0 | 1 | 0 | 3 | 0 | 5 | 6 | 1 | 0 | 3 | 0 | 1 | 0 | -----------------------------------------------------
Con una matriz de longitud P de este tipo, podemos encontrar la longitud de la subcadena palindrómica más larga al observar el elemento máximo de P. Es decir,
P [i] es la longitud de una subcadena palindrómica con centro en i en la cadena transformada T, es decir. centro en i / 2 en la cadena S original; Por lo tanto, la subcadena palindrómica más larga sería la subcadena de la longitud P [i max ] a partir del índice (i max -P [i max ]) / 2, de modo que i max es el índice del elemento máximo en P.
Vamos a dibujar una figura similar en el siguiente para nuestro ejemplo no palindrómico cadena S = "babaabca".
min c max |----------------|-----------------| -------------------------------------------------------------------- idx= | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16| --------------------------------------------------------------------- T=| $ | b | $ | a | $ | b | $ | a | $ | a | $ | b | $ | c | $ | a | $ | --------------------------------------------------------------------- P=| 0 | 1 | 0 | 3 | 0 | 3 | 0 | 1 | 4 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | ---------------------------------------------------------------------
La pregunta es cómo calcular P de manera eficiente. La propiedad simétrica sugiere los siguientes casos que potencialmente podríamos usar para calcular P [i] usando P [i ''] previamente calculado en el índice espejo i'' de la izquierda, omitiendo así una gran cantidad de cálculos. Supongamos que tenemos un palíndromo de referencia (primer palíndromo) para comenzar.
Un tercer palíndromo cuyo centro se encuentra en el lado derecho de un primer palíndromo tendrá exactamente la misma longitud que el de un segundo palíndromo anclado en el centro del espejo en el lado izquierdo, si el segundo palíndromo está dentro de los límites del primer palíndromo en al menos un personaje.
Por ejemplo, en la siguiente figura con el primer palíndromo centrado en c = 8 y delimitado por min = 4 y max = 12, la longitud del tercer palíndromo centrado en i = 9 (con índice espejo i ''= 2 * ci = 7) es , P [i] = P [i ''] = 1. Esto se debe a que el segundo palíndromo centrado en i'' está dentro de los límites del primer palíndromo. Del mismo modo, P [10] = P [6] = 0.|----3rd----| |----2nd----| |-----------1st Palindrome---------| min i'' c i max |------------|---|---|-------------| -------------------------------------------------------------------- idx= | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16| --------------------------------------------------------------------- T=| $ | b | $ | a | $ | b | $ | a | $ | a | $ | b | $ | c | $ | a | $ | --------------------------------------------------------------------- P=| 0 | 1 | 0 | 3 | 0 | 3 | 0 | 1 | 4 | ? | ? | ? | ? | ? | ? | ? | ? | --------------------------------------------------------------------- Ahora, la pregunta es ¿cómo verificar este caso? Tenga en cuenta que, debido a la propiedad simétrica, la longitud del segmento [min..i ''] es igual a la longitud del segmento [i..max]. Además, tenga en cuenta que el segundo palíndromo está completamente dentro del primer palíndromo si el borde izquierdo del segundo palíndromo está dentro del límite izquierdo, min del primer palíndromo. Es decir,
i''-P[i''] >= min =>P[i'']-i'' < -min (negate) =>P[i''] < i''-min =>P[i''] < max-i [(max-i)=(i''-min) due to symmetric property]. Combinando todos los hechos en el caso 1,
P [i] = P [i ''], iff (max-i)> P [i'']
Si el segundo palíndromo se encuentra o se extiende más allá del límite izquierdo del primer palíndromo, se garantiza que el tercer palíndromo tendrá al menos la longitud desde su propio centro hasta el carácter más externo derecho del primer palíndromo. Esta longitud es la misma desde el centro del segundo palíndromo al carácter más externo izquierdo del primer palíndromo.
Por ejemplo, en la siguiente figura, el segundo palíndromo centrado en i = 5 se extiende más allá del límite izquierdo del primer palíndromo. Entonces, en este caso no podemos decir P [i] = P [i '']. Pero la longitud del tercer palíndromo centrado en i = 11, P [i] es al menos la longitud desde su centro i = 11 hasta el límite derecho máximo = 12 del primer palíndromo centrado en c. Es decir, P [i]> = 1. Esto significa que el tercer palíndromo podría extenderse más allá del máximo si y solo si el carácter inmediato siguiente, el máximo, coincide exactamente con el carácter reflejado, y continuamos este control más allá. Por ejemplo, en este caso P [13]! = P [9] y no se puede extender. Entonces, P [i] = 1.|-------2nd palindrome------| |----3rd----|---? |-----------1st Palindrome---------| min i'' c i max |----|-----------|-----------|-----| -------------------------------------------------------------------- idx= | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16| --------------------------------------------------------------------- T=| $ | b | $ | a | $ | b | $ | a | $ | a | $ | b | $ | c | $ | a | $ | --------------------------------------------------------------------- P=| 0 | 1 | 0 | 3 | 0 | 3 | 0 | 1 | 4 | 1 | 0 | ? | ? | ? | ? | ? | ? | --------------------------------------------------------------------- Entonces, ¿cómo verificar este caso? Esto es simplemente el cheque fallido para el caso 1. Es decir, el segundo palíndromo se extenderá más allá del borde izquierdo del primer palíndromo iff,
i''-P[i''] < min =>P[i'']-i'' >= -min [negate] =>P[i''] >= i''-min =>P[i''] >= max-i [(max-i)=(i''-min) due to symmetric property]. Es decir, P [i] es al menos (max-i) iff (max-i) P [i]> = (max-i), iff (max-i) Ahora, si el tercer palíndromo se extiende más allá del máximo, entonces necesitamos actualizar el centro y el límite del nuevo palíndromo.
Si el palíndromo centrado en i se expande en el pasado, entonces tenemos un palíndromo nuevo (extendido), de ahí un nuevo centro en c = i. Actualizar el máximo al límite más a la derecha del nuevo palíndromo.
Combinando todos los hechos en el caso 1 y el caso 2, podemos llegar a una pequeña y hermosa fórmula:Case 1: P[i] = P[i''], iff (max-i) > P[i''] Case 2: P[i]>=(max-i), iff (max-i) = min(P[i''], max-i).
Es decir, P [i] = min (P [i ''], max-i) cuando el tercer palíndromo no puede extenderse más allá de máx. De lo contrario, tenemos un tercer tercer palíndromo en el centro en c = iy un nuevo máximo = i + P [i].
Ni el primer ni el segundo palíndromo proporcionan información para ayudar a determinar la longitud palindrómica de un cuarto palíndromo cuyo centro está fuera del lado derecho del primer palíndromo.
Es decir, no podemos determinar preventivamente P [i] si i> max. Es decir,P [i] = 0, iff max-i <0
Combinando todos los casos, concluimos las fórmulas:P [i] = max> i? min (P [i ''], max-i): 0. En caso de que podamos expandirnos más allá de max, nos expandiremos haciendo coincidir caracteres más allá del máximo con el carácter reflejado con respecto al nuevo centro en c = i. Finalmente, cuando tenemos una discrepancia, actualizamos la nueva max = i + P [i].
Referencia: descripción del algoritmo en la página wiki
El Algoritmo en este sitio parece comprensible para el cierto punto http://www.akalin.cx/longest-palindrome-linear-time
Para comprender este enfoque particular, lo mejor es tratar de resolver el problema en papel y detectar los trucos que puede implementar para evitar buscar el palíndromo para cada centro posible.
Primero respóndese a sí mismo: cuando encuentre un palíndromo de una longitud determinada, digamos 5, ¿no puede, como próximo paso, saltar hasta el final de este palíndromo (omitiendo 4 letras y 4 letras a la mitad)?
Si intentas crear un palíndromo con una longitud de 8 y colocas otro palíndromo con una longitud> 8, cuyo centro está en el lado derecho del primer palíndromo notarás algo gracioso. Pruébelo: Palíndromo con longitud 8 - WOWILIKEEKIL - Me gusta + ekiL = 8 Ahora, en la mayoría de los casos, podría escribir el lugar entre dos E como centro y el número 8 como la longitud y el salto después de la última L para buscar el centro del palíndromo más grande.
Este enfoque no es correcto, ya que el centro del palíndromo más grande puede estar dentro de ekiL y lo extrañarías si saltaras después de la última L.
Después de encontrar LIKE + EKIL, coloca 8 en la matriz que utilizan estos algos y esto se ve así:
[0,1,0,3,0,1,0,1,0,3,0,1,0,1,0,1,8]
para
[#,WOW ME GUSTA,#]
El truco es que ya sabes que muy probablemente los siguientes 7 (8-1) números después de 8 serán los mismos que en el lado izquierdo, por lo que el siguiente paso es copiar automáticamente 7 números de la izquierda de 8 a la derecha de 8 manteniendo importa que aún no sean definitivos. La matriz se vería así
[0,1,0,3,0,1,0,1,0,3,0,1,0,1,0,1,8,1,0,1,0,1,0,3] ( estamos en 8)
para
[#, W, #, O, #, W, #, I, #, L, #, I, #, K, #, E, #, E, #, K, #, I, #, L]
Hagamos un ejemplo, ese salto destruiría nuestra solución actual y vería lo que podemos notar.
WOWILIKEEKIL - intentemos hacer un palíndromo más grande con el centro en algún lugar dentro de EKIL. Pero no es posible, tenemos que cambiar la palabra EKIL por algo que contenga palíndromo. ¿Qué? OOOOOh - ese es el truco. La única posibilidad de tener un palíndromo más grande con el centro en el lado derecho de nuestro palíndromo actual es que ya está en el lado derecho (e izquierdo) del palíndromo.
Probemos construir uno basado en WOWILIKEEKIL. Tendríamos que cambiar EKIL a, por ejemplo, EKIK con I como centro del palíndromo más grande; recuerde cambiar LIKE a KIKE también. Las primeras letras de nuestro palíndromo complicado serán:
WOWIKIKEEKIK
como dije antes, que el último sea el centro del gran pálinario de KIKEEKIK:
WOWIKIKEEKIKEEKIKIW
hagamos la matriz hasta nuestro antiguo pallindrom y descubramos cómo aprovechar la información adicional.
para
[_ W _ O _ W _ I _ K _ I _ K _ E _ E _ K _ I _ K _ E _ E _ K _ I _ K _ I _ W]
será [0,1,0,3,0,1,0,1,0,3,0,3,0,1,0,1,8
sabemos que el próximo I - 3 será el pallindrome más largo, pero olvidémonos un poco. Copiemos los números en la matriz de la izquierda de 8 a la derecha (8 números)
[0,1,0,3,0,1,0,1,0,3,0,3,0,1,0,1,8,1,0,1,0,3,0,3]
En nuestro ciclo, estamos entre E con el número 8. ¿Qué tiene de especial I (futuro centro del mayor pállino) que no podemos ir directamente a K (la última letra del mayor relieve actual)? Lo especial es que excede el tamaño actual de la matriz ... ¿cómo? Si mueve 3 espacios a la derecha de 3, está fuera de la matriz. Significa que puede ser el medio del mayor pallindrome y lo más lejos que puedes saltar es esta letra I.
Perdón por la longitud de esta respuesta. Quería explicarle el algoritmo y puedo asegurarle que @OmnipotentEntity tenía razón. Lo entiendo incluso mejor después de explicárselo :)
Este material es de gran ayuda para que lo entienda: http://solutionleetcode.blogspot.com/2013/07/leetcode-longest-palindromic-substring.html
Defina T como la longitud de las subcadenas palindrómicas más largas centradas en cada uno de los caracteres.
La clave es que cuando los palíndromos más pequeños están completamente incrustados dentro del palíndromo más largo, T [i] también debe ser simétrica dentro del palíndromo más largo.
De lo contrario, tendremos que calcular T [i] desde cero, en lugar de calcular desde la parte izquierda simétrica.
Estoy de acuerdo en que la lógica no es del todo correcta en la explicación del enlace. Doy algunos detalles a continuación.
El algoritmo de Manacher rellena una tabla P [i] que contiene cuánto se extiende el palíndromo centrado en i. Si P [5] = 3, entonces tres caracteres en cualquier lado de la posición cinco son parte del palíndromo. El algoritmo aprovecha el hecho de que si ha encontrado un palíndromo largo, puede completar los valores de P en el lado derecho del palíndromo mirando los valores de P en el lado izquierdo, ya que deberían ser principalmente el mismo.
Comenzaré por explicar el caso del que estaba hablando, y luego ampliaré esta respuesta según sea necesario.
R indica el índice del lado derecho del palíndromo centrado en C. Aquí está el estado en el lugar que indicó:
C=11
R=20
i=15
i''=7
P[i'']=7
R-i=5
y la lógica es así:
if P[i'']<=R-i: // not true
else: // P[i] is at least 5, but may be greater
El pseudocódigo en el enlace indica que P [i] debería ser mayor o igual que P [i ''] si la prueba falla, pero creo que debería ser mayor o igual a Ri, y la explicación lo respalda.
Como P [i ''] es mayor que Ri, el palíndromo centrado en i'' se extiende más allá del palíndromo centrado en C. Sabemos que el palíndromo centrado en i tendrá al menos caracteres de Ri de ancho, porque todavía tenemos simetría hasta ese punto, pero tenemos que buscar explícitamente más allá de eso.
Si P [i ''] no hubiera sido mayor que Ri, entonces el palíndromo más grande centrado en i'' está dentro del palíndromo más grande centrado en C, entonces habríamos sabido que P [i] no podría ser más grande que P [i '']. Si lo fuera, tendríamos una contradicción. Significaría que podríamos ampliar el palíndromo centrado en i más allá de P [i ''], pero si pudiéramos, también podríamos extender el palíndromo centrado en i'' debido a la simetría, pero ya estaba se supone que es lo más grande posible.
Este caso se ilustra anteriormente:
C=11
R=20
i=13
i''=9
P[i'']=1
R-i=7
En este caso, P [i ''] <= Ri. Como todavía estamos a 7 caracteres del borde del palíndromo centrado en C, sabemos que al menos 7 caracteres alrededor de i son los mismos que los 7 caracteres alrededor de i ''. Como solo había un palíndromo de un carácter alrededor de mí, también hay un palíndromo de un carácter alrededor de mí.
j_random_hacker notó que la lógica debería ser más como esto:
if P[i'']<R-i then
P[i]=P[i'']
else if P[i'']>R-i then
P[i]=R-i
else P[i]=R-i + expansion
Si P [i ''] <Ri, entonces sabemos que P [i] == P [i''], ya que todavía estamos dentro del palíndromo centrado en C.
Si P [i '']> Ri, entonces sabemos que P [i] == Ri, porque de lo contrario el palíndromo centrado en C habría pasado pasado R.
Entonces, la expansión realmente solo es necesaria en el caso especial donde P [i ''] == Ri, por lo que no sabemos si el palíndromo en P [i] puede ser más largo.
Esto se maneja en el código real al establecer P [i] = min (P [i ''], Ri) y luego siempre se expande. Esta forma de hacerlo no aumenta la complejidad del tiempo, ya que si no es necesaria una expansión, el tiempo necesario para realizar la expansión es constante.
He encontrado una de las mejores explicaciones hasta el momento en el siguiente enlace:
http://tarokuriyama.com/projects/palindrome2.php
También tiene una visualización para el mismo ejemplo de cuerda (babcbabcbaccba) utilizado en el primer enlace mencionado en la pregunta.
Además de este enlace, también encontré el código en
http://algs4.cs.princeton.edu/53substring/Manacher.java.html
Espero que sea útil para otros que intentan entender el quid de este algoritmo.
Hice un video sobre este algoritmo usando gráficos de animación. ¡Espero que te ayude a entenderlo! https://www.youtube.com/watch?v=kbUiR5YWUpQ
class Palindrome
{
private int center;
private int radius;
public Palindrome(int center, int radius)
{
if (radius < 0 || radius > center)
throw new Exception("Invalid palindrome.");
this.center = center;
this.radius = radius;
}
public int GetMirror(int index)
{
int i = 2 * center - index;
if (i < 0)
return 0;
return i;
}
public int GetCenter()
{
return center;
}
public int GetLength()
{
return 2 * radius;
}
public int GetRight()
{
return center + radius;
}
public int GetLeft()
{
return center - radius;
}
public void Expand()
{
++radius;
}
public bool LargerThan(Palindrome other)
{
if (other == null)
return false;
return (radius > other.radius);
}
}
private static string GetFormatted(string original)
{
if (original == null)
return null;
else if (original.Length == 0)
return "";
StringBuilder builder = new StringBuilder("#");
foreach (char c in original)
{
builder.Append(c);
builder.Append(''#'');
}
return builder.ToString();
}
private static string GetUnFormatted(string formatted)
{
if (formatted == null)
return null;
else if (formatted.Length == 0)
return "";
StringBuilder builder = new StringBuilder();
foreach (char c in formatted)
{
if (c != ''#'')
builder.Append(c);
}
return builder.ToString();
}
public static string FindLargestPalindrome(string str)
{
string formatted = GetFormatted(str);
if (formatted == null || formatted.Length == 0)
return formatted;
int[] radius = new int[formatted.Length];
try
{
Palindrome current = new Palindrome(0, 0);
for (int i = 0; i < formatted.Length; ++i)
{
radius[i] = (current.GetRight() > i) ?
Math.Min(current.GetRight() - i, radius[current.GetMirror(i)]) : 0;
current = new Palindrome(i, radius[i]);
while (current.GetLeft() - 1 >= 0 && current.GetRight() + 1 < formatted.Length &&
formatted[current.GetLeft() - 1] == formatted[current.GetRight() + 1])
{
current.Expand();
++radius[i];
}
}
Palindrome largest = new Palindrome(0, 0);
for (int i = 0; i < radius.Length; ++i)
{
current = new Palindrome(i, radius[i]);
if (current.LargerThan(largest))
largest = current;
}
return GetUnFormatted(formatted.Substring(largest.GetLeft(), largest.GetLength()));
}
catch (Exception ex)
{
Console.WriteLine(ex);
}
return null;
}
using namespace std;
class Palindrome{
public:
Palindrome(string st){
s = st;
longest = 0;
maxDist = 0;
//ascii: 126(~) - 32 (space) = 94
// for ''a'' to ''z'': vector<vector<int>> v(26,vector<int>(0));
vector<vector<int>> v(94,vector<int>(0)); //all ascii
mDist.clear();
vPos = v;
bDebug = true;
};
string s;
string sPrev; //previous char
int longest; //longest palindrome size
string sLongest; //longest palindrome found so far
int maxDist; //max distance been checked
bool bDebug;
void findLongestPal();
int checkIfAnchor(int iChar, int &i);
void checkDist(int iChar, int i);
//store char positions in s pos[0] : ''a''... pos[25] : ''z''
// 0123456
// i.e. "axzebca" vPos[0][0]=0 (1st. position of ''a''), vPos[0][1]=6 (2nd pos. of ''a''),
// vPos[25][0]=2 (1st. pos. of ''z'').
vector<vector<int>> vPos;
//<anchor,distance to check>
// i.e. abccba anchor = 3: position of 2nd ''c'', dist = 3
// looking if next char has a dist. of 3 from previous one
// i.e. abcxcba anchor = 4: position of 2nd ''c'', dist = 4
map<int,int> mDist;
};
//check if current char can be an anchor, if so return next distance to check (3 or 4)
// i.e. "abcdc" 2nd ''c'' is anchor for sub-palindrome "cdc" distance = 4 if next char is ''b''
// "abcdd: 2nd ''d'' is anchor for sub-palindrome "dd" distance = 3 if next char is ''c''
int Palindrome::checkIfAnchor(int iChar, int &i){
if (bDebug)
cout<<"checkIfAnchor. i:"<<i<<" iChar:"<<iChar<<endl;
int n = s.size();
int iDist = 3;
int iSize = vPos[iChar].size();
//if empty or distance to closest same char > 2
if ( iSize == 0 || vPos[iChar][iSize - 1] < (i - 2)){
if (bDebug)
cout<<" .This cannot be an anchor! i:"<<i<<" : iChar:"<<iChar<<endl;
//store char position
vPos[iChar].push_back(i);
return -1;
}
//store char position of anchor for case "cdc"
vPos[iChar].push_back(i);
if (vPos[iChar][iSize - 1] == (i - 2))
iDist = 4;
//for case "dd" check if there are more repeated chars
else {
int iRepeated = 0;
while ((i+1) < n && s[i+1] == s[i]){
i++;
iRepeated++;
iDist++;
//store char position
vPos[iChar].push_back(i);
}
}
if (bDebug)
cout<<" .iDist:"<<iDist<<" i:"<<i<<endl;
return iDist;
};
//check distance from previous same char, and update sLongest
void Palindrome::checkDist(int iChar, int i){
if (bDebug)
cout<<"CheckDist. i:"<<i<<" iChar:"<<iChar<<endl;
int iDist;
int iSize = vPos[iChar].size();
bool b1stOrLastCharInString;
bool bDiffDist;
//checkAnchor will add this char position
if ( iSize == 0){
if (bDebug)
cout<<" .1st time we see this char. Assign it INT_MAX Dist"<<endl;
iDist = INT_MAX;
}
else {
iDist = i - vPos[iChar][iSize - 1];
}
//check for distances being check, update them if found or calculate lengths if not.
if (mDist.size() == 0) {
if (bDebug)
cout<<" .no distances to check are registered, yet"<<endl;
return;
}
int i2ndMaxDist = 0;
for(auto it = mDist.begin(); it != mDist.end();){
if (bDebug)
cout<<" .mDist. anchor:"<<it->first<<" . dist:"<<it->second<<endl;
b1stOrLastCharInString = false;
bDiffDist = it->second == iDist; //check here, because it can be updated in 1st. if
if (bDiffDist){
if (bDebug)
cout<<" .Distance checked! :"<<iDist<<endl;
//check if it''s the first char in the string
if (vPos[iChar][iSize - 1] == 0 || i == (s.size() - 1))
b1stOrLastCharInString = true;
//we will continue checking for more...
else {
it->second += 2; //update next distance to check
if (it->second > maxDist) {
if (bDebug)
cout<<" .previous MaxDist:"<<maxDist<<endl;
maxDist = it->second;
if (bDebug)
cout<<" .new MaxDist:"<<maxDist<<endl;
}
else if (it->second > i2ndMaxDist) {//check this...hmtest
i2ndMaxDist = it->second;
if (bDebug)
cout<<" .second MaxDist:"<<i2ndMaxDist<<endl;
}
it++;
}
}
if (!bDiffDist || b1stOrLastCharInString) {
if (bDebug && it->second != iDist)
cout<<" .Dist diff. Anchor:"<<it->first<<" dist:"<<it->second<<" iDist:"<<iDist<<endl;
else if (bDebug)
cout<<" .Palindrome found at the beggining or end of the string"<<endl;
//if we find a closest same char.
if (!b1stOrLastCharInString && it->second > iDist){
if (iSize > 1) {
if (bDebug)
cout<<" . < Dist . looking further..."<<endl;
iSize--;
iDist = i - vPos[iChar][iSize - 1];
continue;
}
}
if (iDist == maxDist) {
maxDist = 0;
if (bDebug)
cout<<" .Diff. clearing Max Dist"<<endl;
}
else if (iDist == i2ndMaxDist) {
i2ndMaxDist = 0;
if (bDebug)
cout<<" .clearing 2nd Max Dist"<<endl;
}
int iStart;
int iCurrLength;
//first char in string
if ( b1stOrLastCharInString && vPos[iChar].size() > 0 && vPos[iChar][iSize - 1] == 0){
iStart = 0;
iCurrLength = i+1;
}
//last char in string
else if (b1stOrLastCharInString && i == (s.size() - 1)){
iStart = i - it->second;
iCurrLength = it->second + 1;
}
else {
iStart = i - it->second + 1;
iCurrLength = it->second - 1; //"xabay" anchor:2nd. ''a''. Dist from ''y'' to ''x'':4. length ''aba'':3
}
if (iCurrLength > longest){
if (bDebug)
cout<<" .previous Longest!:"<<sLongest<<" length:"<<longest<<endl;
longest = iCurrLength;
sLongest = s.substr(iStart, iCurrLength);
if (bDebug)
cout<<" .new Longest!:"<<sLongest<<" length:"<<longest<<endl;
}
if (bDebug)
cout<<" .deleting iterator for anchor:"<<it->first<<" dist:"<<it->second<<endl;
mDist.erase(it++);
}
}
//check if we need to get new max distance
if (maxDist == 0 && mDist.size() > 0){
if (bDebug)
cout<<" .new maxDist needed";
if (i2ndMaxDist > 0) {
maxDist = i2ndMaxDist;
if (bDebug)
cout<<" .assigned 2nd. max Dist to max Dist"<<endl;
}
else {
for(auto it = mDist.begin(); it != mDist.end(); it++){
if (it->second > maxDist)
maxDist = it->second;
}
if (bDebug)
cout<<" .new max dist assigned:"<<maxDist<<endl;
}
}
};
void Palindrome::findLongestPal(){
int n = s.length();
if (bDebug){
cout<<"01234567891123456789212345"<<endl<<"abcdefghijklmnopqrstuvwxyz"<<endl<<endl;
for (int i = 0; i < n;i++){
if (i%10 == 0)
cout<<i/10;
else
cout<<i;
}
cout<<endl<<s<<endl;
}
if (n == 0)
return;
//process 1st char
int j = 0;
//for ''a'' to ''z'' : while (j < n && (s[j] < ''a'' && s[j] > ''z''))
while (j < n && (s[j] < '' '' && s[j] > ''~''))
j++;
if (j > 0){
s.substr(j);
n = s.length();
}
// for ''a'' to ''z'' change size of vector from 94 to 26 : int iChar = s[0] - ''a'';
int iChar = s[0] - '' '';
//store char position
vPos[iChar].push_back(0);
for (int i = 1; i < n; i++){
if (bDebug)
cout<<"findLongestPal. i:"<<i<<" "<<s.substr(0,i+1)<<endl;
//if max. possible palindrome would be smaller or equal
// than largest palindrome found then exit
// (n - i) = string length to check
// maxDist: max distance to check from i
int iPossibleLongestSize = maxDist + (2 * (n - i));
if ( iPossibleLongestSize <= longest){
if (bDebug)
cout<<" .PosSize:"<<iPossibleLongestSize<<" longest found:"<<iPossibleLongestSize<<endl;
return;
}
//for ''a'' to ''z'' : int iChar = s[i] - ''a'';
int iChar = s[i] - '' '';
//for ''a'' to ''z'': if (iChar < 0 || iChar > 25){
if (iChar < 0 || iChar > 94){
if (bDebug)
cout<<" . i:"<<i<<" iChar:"<<s[i]<<" skipped!"<<endl;
continue;
}
//check distance to previous char, if exist
checkDist(iChar, i);
//check if this can be an anchor
int iDist = checkIfAnchor(iChar,i);
if (iDist == -1)
continue;
//append distance to check for next char.
if (bDebug)
cout<<" . Adding anchor for i:"<<i<<" dist:"<<iDist<<endl;
mDist.insert(make_pair(i,iDist));
//check if this is the only palindrome, at the end
//i.e. "......baa" or "....baca"
if (i == (s.length() - 1) && s.length() > (iDist - 2)){
//if this is the longest palindrome!
if (longest < (iDist - 1)){
sLongest = s.substr((i - iDist + 2),(iDist - 1));
}
}
}
};
int main(){
string s;
cin >> s;
Palindrome p(s);
p.findLongestPal();
cout<<p.sLongest;
return 0;
}