La subsecuencia más larga sin cadena

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

Parece que esto podría ser un problema DP de 2 estados, con el estado [s_pos, t_pos] siendo la subsecuencia más larga de la cadena S que comienza en s_pos que no tiene la picadura T [t_pos..M] como una 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 aparece el caso donde S = aaabcy T = aabc. El problema está en la declaración else : no sé cómo hacer la transición si los caracteres son iguales. En realidad siento que si la rama está mal ... ¿Alguien sabe qué podría estar mal?

Incluso falla el caso S = aaaby T = aab. Puedo explicar por qué falla: suponiendo que llamo a resolver (0, 0). resolver (0, 0) llama a resolver (1, 1). resolver (1, 1) llama a resolver (2, 2). Como s [2]! = T [2], reinicia la búsqueda desde resolver (3, 0). Sin embargo, aab es una subcadena y nunca verifica esto o 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;
}

Esto debería funcionar. Lo escribí en un metacó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

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

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

Yo iría con el enfoque iterativo.

Crearía una lista vacía fuera de la función.

Entonces llama solve.

En esta función, intente este enfoque:

Recorrer la cadena: si el carácter actual no es el comienzo de la subsecuencia, coloque el carácter en una cadena de retención. Esto construirá una cadena. Si comienza la subsecuencia, agregue esos caracteres a otra cadena de retención. Marca cuántos partidos tienes contra la subsecuencia. Uno de cada carácter, si ya coincide con la subsecuencia, luego mire para ver si coincide con el primer carácter, y luego si coincide con el carácter en la siguiente posición que coincida. Si coincide con la subsecuencia, todo lo anterior (en la cadena de retención) se coloca en la lista.

Entonces, básicamente necesita rastrear lo que puede ser una secuencia posible que puede ganar, y necesita 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 revise varios ejemplos y anote lo que está sucediendo en cada paso hasta que vea si existe la necesidad de otra cadena de retención.

Creo que debe tratar la subcadena Y como una expresión regular y transformarla en un DFA. Luego pasa la entrada a través del DFA, rastreando cuánto tiempo ha pasado desde que tuvo una coincidencia. Parece un problema de tiempo lineal, suponiendo que el tamaño de la entrada es mucho mayor que la complejidad de la cadena coincidente.