algorithm - significado - lista de sufijos

El palíndromo más largo en una cadena usando el árbol de sufijos

Question

Intentaba encontrar el palíndromo más largo en una cuerda. La solución de fuerza bruta toma O (n ^ 3) tiempo. Leí que hay un algoritmo de tiempo lineal para usar árboles de sufijos. Estoy familiarizado con los sufijos y me siento cómodo construyéndolos. ¿Cómo se usa el árbol de sufijo incorporado para encontrar el palíndromo más largo?

Answer 1

Creo que debes avanzar de esta manera:

Deja que y ₁ y ₂ ... _yn sea ​​tu cadena (donde y _yo somos letras).

Cree el árbol sufijo generalizado de S _f = y ₁ y ₂ ... y _n $ y S _r = y _n y _{n - 1} ... y ₁ # (invierta las letras y elija diferentes caracteres finales para S _f ($) y S _r (#)) ... donde S _f significa "Cadena, Adelante" y S _r significa "Cadena, Reversa" .

Para cada sufijo i en S _f , encuentre el ancestro común más bajo con el sufijo n - i + 1 en S _r .

Lo que va desde la raíz hasta este antepasado común más bajo es un palíndromo, porque ahora el ancestro común más bajo representa el prefijo común más largo de estos dos sufijos. Recordar que:

(1) Un prefijo de un sufijo es una subcadena .

(2) Un palíndromo es una cadena idéntica a su reverso.

(3) Entonces, el palíndromo más largo contenido dentro de una cuerda es exactamente la subcadena común más larga de esta cuerda y su reverso.

(4) Por lo tanto, el palíndromo más largo contenido dentro de una cadena es exactamente el prefijo común más largo de todos los pares de sufijos entre una cadena y su reverso. Esto es lo que estamos haciendo aquí.

EJEMPLO

Tomemos la palabra banana .

S _f = banana $

S _r = ananab #

A continuación se muestra el árbol sufijo generalizado de S _f y S _r , donde el número al final de cada ruta es el índice del sufijo correspondiente. Hay un pequeño error, el común a todas las 3 ramas del padre de Blue_4 debe estar en su borde de entrada, al lado de n :

El nodo interior más bajo en el árbol es la subcadena común más larga de esta cadena y su reverso. Al observar todos los nodos interiores del árbol, encontrará el palíndromo más largo.

El palíndromo más largo se encuentra entre Green_0 y Blue_1 (es decir, banana y anana ) y es anana

EDITAR

Acabo de encontrar este artículo que responde esta pregunta.

Answer 2

Explicación simple y breve de Skiena - The Algorithm Design Manual

Encuentra el palíndromo más largo en S [usando el árbol de sufijos] - Un palíndromo es una cadena que dice lo mismo si el orden de los caracteres se invierte, como madam . Para encontrar el palíndromo más largo en una cadena S, construya un árbol de sufijo único que contenga todos los sufijos de S y la inversión de S, con cada hoja identificada por su posición inicial. Un palíndromo está definido por cualquier nodo en este árbol que tenga niños reenviados e invertidos desde la misma posición.

Answer 3

La solución lineal se puede encontrar de esta manera ::

Prequisiciones:

(1) Debe saber cómo construir la matriz de sufijos en O (N) u O (NlogN).

(2) Debe saber cómo encontrar la matriz LCP estándar, es decir. LCP entre sufijos adyacentes i y i-1

es decir. LCP [i] = LCP (sufijo i en matriz ordenada, sufijo i-1 en matriz ordenada) para (i> 0).

Deje que S sea ​​la cadena original y S '' sea ​​el reverso de la secuencia original. Tomemos S = " banana " como ejemplo. Luego su cadena inversa S ''= ananab.

Paso 1 : Concatenar S + # + S '' para obtener String Str, donde # es un alfabeto que no está presente en el String original.

    Concatenated String Str=S+#+S''
    Str="banana#ananab"

Paso 2: Ahora construye la matriz de sufijos de la cadena Str.

En este ejemplo, la matriz de sufijos es:

Suffix Number   Index   Sorted Suffix
0               6       #ananab
1               5       a#ananab
2               11      ab
3               3       ana#ananab
4               9       anab
5               1       anana#ananab
6               7       ananab
7               12      b
8               0       banana#ananab
9               4       na#ananab
10              10      nab
11              2       nana#ananab
12              8       nanab

Tenga en cuenta que una matriz de sufijos es una matriz de enteros que da las posiciones de inicio de los sufijos de una cadena en orden lexicográfico. Por lo tanto, la matriz que contiene el índice de la posición inicial es un sufijo matriz.

Eso es SuffixArray [] = {6,5,11,3,9,1,7,12,0,4,10,2,8};

Paso 3 : A medida que ha logrado construir la matriz de sufijos, ahora encuentre los prefijos comunes más largos entre los sufijos adyacentes .

LCP between #ananab        a#ananab          is :=0
LCP between a#ananab       ab                is :=1
LCP between ab             ana#ananab        is :=1
LCP between ana#ananab     anab              is :=3
LCP between anab           anana#ananab      is :=3
LCP between anana#ananab   ananab            is :=5
LCP between ananab         b                 is :=0
LCP between b              banana#ananab     is :=1
LCP between banana#ananab  na#ananab         is :=0
LCP between na#ananab      nab               is :=2
LCP between nab            nana#ananab       is :=2
LCP between nana#ananab nanab                is :=4

Por lo tanto, LCP array LCP = {0,0,1,1,3,3,5,0,1,0,2,2,4}.

Donde LCP [i] = Longitud del prefijo común más largo entre sufijo iy sufijo (i-1). (para i> 0)

Etapa 4:

Ahora que ha construido una matriz LCP, use la siguiente lógica.

    Let the length of the Longest Palindrome ,longestlength:=0 (Initially)
    Let Position:=0.
    for(int i=1;i<Len;++i)
    {
        //Note that Len=Length of Original String +"#"+ Reverse String
        if((LCP[i]>longestlength))
        {
            //Note Actual Len=Length of original Input string .
            if((suffixArray[i-1]<actuallen && suffixArray[i]>actuallen)||(suffixArray[i]<actuallen && suffixArray[i-1]>actuallen))
            {
                 //print :Calculating Longest Prefixes b/w suffixArray[i-1] AND  suffixArray[i]


                longestlength=LCP[i];
              //print The Longest Prefix b/w them  is ..
              //print The Length is :longestlength:=LCP[i];
                Position=suffixArray[i];
            }
        }
    }
    So the length of Longest Palindrome :=longestlength;
    and the longest palindrome is:=Str[position,position+longestlength-1];

Ejemplo de ejecución ::

    actuallen=Length of banana:=6
    Len=Length of "banana#ananab" :=13.

Calculating Longest Prefixes b/w a#ananab AND  ab
The Longest Prefix b/w them  is :a 
The Length is :longestlength:= 1 
Position:= 11




Calculating Longest Prefixes b/w ana#ananab AND  anab
The Longest Prefix b/w them  is :ana
The Length is :longestlength:= 3 
Position:=9



Calculating Longest Prefixes b/w anana#ananab AND  ananab
The Longest Prefix b/w them  is :anana
The Length is :longestlength:= 5 
Position:= 7

So Answer =5.
And the Longest Palindrome is :=Str[7,7+5-1]=anana

Solo tome nota ::

La condición if del Paso 4 básicamente hace referencia a que, en cada iteración (i), si tomo los sufijos s1 (i) y s2 (i-1), entonces "s1 debe contener # y s2 no debe contener #" O "s2 debe contener # y s1 no debe contener # ".

 |(1:BANANA#ANANAB)|leaf
tree:|
     |     |      |      |(7:#ANANAB)|leaf
     |     |      |(5:NA)|
     |     |      |      |(13:B)|leaf
     |     |(3:NA)|
     |     |      |(7:#ANANAB)|leaf
     |     |      |
     |     |      |(13:B)|leaf
     |(2:A)|
     |     |(7:#ANANAB)|leaf
     |     |
     |     |(13:B)|leaf
     |
     |      |      |(7:#ANANAB)|leaf
     |      |(5:NA)|
     |      |      |(13:B)|leaf
     |(3:NA)|
     |      |(7:#ANANAB)|leaf
     |      |
     |      |(13:B)|leaf
     |
     |(7:#ANANAB)|leaf

Answer 4

Solución de DP:

int longestPalin(char *str)
{
    n = strlen(str);
    bool table[n][n]l
    memset(table, 0, sizeof(table));
    int start = 0;

    for(int i=0; i<n; ++i)
        table[i][i] = true;
    int maxlen = 1;

    for(int i=0; i<n-1; ++i)
    {
        if(str[i] == str[i+1])
        {
            table[i][i] = true;
            start = i;
            maxlen = 2;
        }
    }

    for(int k=3; k<=n; ++k)
    {
        for(int i=0; i<n-k+1; ++i)
        {
            int j = n+k-1;
            if(str[i] == str[j] && table[i+1][j-1])
            {
                table[i][j] = true;
                if(k > maxlen)
                {
                    start = i;
                    maxlen = k;
                }
            }
        }
    }
    print(str, start, start+maxlen-1);
    return maxlen;
}

Answer 5

Unos años tarde ...

Supongamos que s es la cadena original, y r está invertida. Supongamos también que hemos construido completamente un árbol de sufijo ST usando s .

Nuestro siguiente paso es verificar todos los sufijos de r contra ST . Con cada nuevo sufijo de r , mantendremos un recuento de los primeros k caracteres que hemos comparado con éxito contra un sufijo preexistente en el árbol (es decir, uno de los sufijos de s).

Como ejemplo, digamos que estamos haciendo coincidir el sufijo "RAT" de r , y s contenía algunos sufijos que comienzan con "RA" , pero ninguno que coincidía con "RAT" . k sería igual a 2 cuando finalmente tuvimos que abandonar la esperanza para los personajes finales "T" . Emparejamos los primeros dos caracteres del sufijo de r con los dos primeros caracteres del sufijo de s. Llamaremos a este nodo que llegamos a n .

Ahora, ¿cómo sabemos cuando encontramos un palíndromo? Al marcar todos los nodos de hoja bajo n .

En un árbol de sufijo tradicional, el índice inicial de cada sufijo se almacena en el nodo hoja de esa rama de sufijo. En nuestro ejemplo anterior, s puede contener un grupo de sufijos que comienzan con "RA" , cada uno de los cuales comienza en uno de los índices presentes en los descendientes del nodo hoja de n .

Usemos estos índices.

¿Qué significa si unimos k caracteres de una de las subcadenas de R contra k caracteres en ST ? Bueno, simplemente significa que encontramos algo de cadena invertida. Pero, ¿qué significa si la ubicación donde comienza la subcadena en R es igual a la subcadena coincidente en S plus k ? Sí, significa que s[i] through s[i+k] dice lo mismo que s[i+k] through s[i] . Y entonces, sea una definición, hemos localizado un palíndromo de tamaño k .

Ahora, todo lo que tienes que hacer es mantener una pestaña en el palíndromo más largo encontrado hasta ahora, y devolverlo al final de tu función.