La subsecuencia más larga sin cadena

8

¿Existe un algoritmo de programación dinámico para encontrar la subsecuencia más larga en una cadena X que no contenga Y como subcadena? Solo que este problema parece tan similar a otros algoritmos de cadena DP, como la subsecuencia y cadena común más largas. Debe ser capaz de manejar las ocurrencias de Y que se superponen.

Parece que esto podría ser un problema de DP de 2 estados, siendo el estado [s_pos, t_pos] la subsecuencia más larga de la cadena S a partir de s_pos que no tiene la cadena T [t_pos..M] como subcadena. N es la longitud de la cadena S y M es la longitud de la cadena T. Sin embargo, mis transiciones no son correctas: no es el caso donde S = aaabc y T = aabc . El problema está en la declaración else : no sé cómo realizar la transición si los caracteres son iguales. En realidad creo que la rama si está equivocada ... ¿alguien sabe qué podría estar mal?

Incluso falla el caso S = aaab y T = aab . Puedo explicar por qué falla: asumiendo que llamo resolver (0, 0). resolver (0, 0) llamadas resolver (1, 1). resolver (1, 1) llamadas resolver (2, 2). Como s [2]! = T [2], se reinicia la búsqueda desde resolver (3, 0). Sin embargo, aab es una subcadena y nunca verifica esto ni considera este caso ...

int solve(int s_pos, int t_pos)
{
    if (s_pos >= N || t_pos >= M) return 0;
    if (t_pos == M - 1 && s[s_pos] == t[t_pos]) return 0;
    int ret = 0;
    if (s[s_pos] != t[t_pos])
    {
        int tmp = solve(s_pos + 1, 0);
        ret = max(ret, tmp + 1);
    }
    else
    {
        for (int i = s_pos + 1; i < N; i++)
        {
            int tmp = solve(i, t_pos + 1);
            if (tmp != 0)
            {
                ret = max(ret, 1 + tmp);
            }
        }
    }
    return ret;
}
    
pregunta user83834 10.03.2013 - 19:15

3 respuestas

1

Esto debería hacer el truco. Lo escribí en un meta código similar al básico.

LONGEST = ""
while N>0
  POS = find(T,S)
  if POS>0 then
    SUB = left(S,POS)
  else
    SUB = S
    POS = N
  endif
  if len(SUB) > len(LONGEST) then
    LONGEST = SUB
  endif
  N = N-POS
wend
    
respondido por el burlip 14.03.2013 - 09:52
0

Creo que el problema principal es su bucle for dentro de la sentencia else, que luego llama a la función de forma recursiva.

Elija un enfoque, ya sea recursivo o iterativo, pero mezclarlos simplemente parece incorrecto.

Iría con el enfoque iterativo.

Me gustaría crear una lista vacía fuera de la función.

Luego llama a solve .

En esta función, intente este enfoque:

Recorre la cadena:   Si el carácter actual no es el inicio de la subsecuencia, coloque el carácter en una cadena de espera. Esto construirá una cadena.   Si comienza la subsecuencia, agregue esos caracteres a otra cadena de espera.   Marca cuántos partidos tienes contra la subsecuencia.   Uno de cada carácter, si ya coincide con la subsecuencia, luego busque si coincide con el primer carácter, y luego si coincide con el carácter en la siguiente posición que debe coincidir.   Si coincide con la subsecuencia, todo lo anterior (en la cadena de espera) se incluirá en la lista.

Por lo tanto, básicamente necesitas rastrear lo que puede ser una posible secuencia que puede ganar, y necesitas rastrear que una subsecuencia puede estar dentro de otra subsecuencia.

Es posible que necesite varias cadenas de retención, pero implemente un enfoque simple, con dos cadenas de retención, luego repase varios ejemplos y anote lo que está sucediendo en cada paso hasta que vea si hay necesidad de otra cadena de retención.

    
respondido por el James Black 12.03.2013 - 02:01
-1

Creo que necesitas tratar la subcadena Y como una expresión regular y transformarla en un DFA. Luego pasa la entrada a través de la DFA, y sigue el tiempo que lleva desde que ha coincidido. Parece un problema de tiempo lineal, suponiendo que el tamaño de la entrada es mucho mayor que la complejidad de la cadena correspondiente.

    
respondido por el NovaDenizen 12.03.2013 - 20:57

Lea otras preguntas en las etiquetas