Sottosequenza più lunga senza stringa

Question

Sottosequenza più lunga senza stringa

#1 da (1 voti)
#2 da (0 voti)
#3 da (-1 voti)

8

Fa esiste un algoritmo di programmazione dinamica per trovare la sottosequenza più lunga in una stringa X che non contiene Y come stringa? Solo che questo problema sembra così simile ad altri algoritmi di stringa DP come la sottosequenza e le stringhe più lunghe comuni. Deve essere in grado di gestire le occorrenze di Y che si sovrappongono.

Sembra che questo potrebbe essere un problema 2-stato DP, con lo Stato [s_pos, t_pos] essendo la sottosequenza più lunga della stringa S a partire da s_pos che non hanno punge T [t_pos..M] come una stringa. N è la lunghezza della stringa S e M è la lunghezza della stringa T. Tuttavia, le transizioni non sono corretti: non ottiene il caso in cui S = aaabc e T = aabc . Il problema è nell'istruzione else - Non so come eseguire la transizione se i caratteri sono uguali. In realtà sento che il ramo if è sbagliato ... qualcuno sa cosa potrebbe essere sbagliato?

Fallisce persino il caso S = aaab e T = aab . Posso spiegare perché fallisce: supponendo chiamo risolva (0, 0). risolvere (0, 0) chiamate risolve (1, 1). risolve (1, 1) chiama risolva (2, 2). Poiché s [2]! = T [2], riavvia la ricerca da solve (3, 0). Tuttavia, aab è una sottostringa e non verifica mai questo o considera questo 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;
}

algorithms strings dynamic-programming

posta user83834 10.03.2013 - 19:15

fonte

3 risposte

Leggi altre domande sui tag algorithms strings dynamic-programming

Quali competenze (tecnologie) diventano obsolete più lente? [chiuso] Python e solo Python per quasi tutte le attività di programmazione! [chiuso]

score 1 · Answer 1

Questo dovrebbe fare il trucco. L'ho scritto in un meta codice simile a quello di base.

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

score 0 · Answer 2

Penso che il problema principale sia il ciclo for all'interno dell'istruzione else, che quindi chiama la funzione in modo ricorsivo.

Scegli un approccio, ricorsivo o iterativo, ma mescolarli sembra solo sbagliato.

Vorrei andare con l'approccio iterativo.

Vorrei creare una lista vuota al di fuori della funzione.

Quindi chiama solve .

In questa funzione prova questo approccio:

Passa attraverso la stringa: Se il carattere corrente non è l'inizio della sottosequenza, metti il personaggio in una stringa di attesa. Questo costruirà una stringa. Se avvia la sottosequenza, aggiungi quei caratteri a un'altra stringa di attesa. Segna quante partite hai contro la sottosequenza. Uno per ogni carattere, se già corrisponde alla sottosequenza, quindi cerca di vedere se corrisponde al primo carattere, quindi se corrisponde al carattere nella posizione successiva da abbinare. Se corrisponde alla sottosequenza, tutto ciò che precede (nella stringa di attesa) viene inserito nell'elenco.

Quindi, in pratica, devi tenere traccia di ciò che potrebbe essere una possibile sequenza che potrebbe vincere, e devi tenere traccia che una sottosequenza può trovarsi all'interno di un'altra sottosequenza.

Potresti aver bisogno di più stringhe di attesa, ma implementare un approccio semplice, con due stringhe di attesa, quindi esaminare vari esempi e annotare ciò che sta accadendo in ogni fase finché non vedi se c'è bisogno di un'altra stringa di attesa.

score -1 · Answer 3

Penso che sia necessario trattare la sottostringa Y come un'espressione regolare e trasformarla in un DFA. Quindi trasmetti l'input tramite DFA, verificando quanto tempo è trascorso da quando hai avuto una corrispondenza. Sembra un problema di tempo lineare, assumendo che la dimensione dell'input sia molto più grande della complessità della stringa corrispondente.