Längste Teilsequenz ohne Zeichenfolge

Gibt es einen dynamischen Programmieralgorithmus, um die längste Teilsequenz in einer Zeichenfolge X zu finden, die Y nicht als Teilzeichenfolge enthält? Nur dass dieses Problem anderen DP-String-Algorithmen wie der längsten gemeinsamen Teilsequenz und dem längsten String so ähnlich zu sein scheint. Es muss in der Lage sein, Vorkommen von Y zu verarbeiten, die sich überlappen.

Es scheint, dass dies ein DP-Problem mit zwei Zuständen sein könnte, wobei der Zustand [s_pos, t_pos] die längste Teilsequenz des Strings S ist, der bei s_pos beginnt und keinen Stich T [t_pos..M] als Teilzeichenfolge hat. N ist die Länge der Zeichenkette S und M ist die Länge der Zeichenkette T. Meine Übergänge sind jedoch nicht korrekt: Es wird nicht der Fall erhalten, in dem S = aaabcund T = aabc. Das Problem liegt in der else- Anweisung - ich weiß nicht, wie ich übergehen soll, wenn die Zeichen gleich sind. Eigentlich habe ich das Gefühl, dass der if-Zweig falsch ist ... weiß jemand, was falsch sein könnte?

Es scheitert sogar der Fall S = aaabund T = aab. Ich kann erklären, warum es fehlschlägt: Angenommen, ich rufe lösen (0, 0). lösen (0, 0) ruft lösen (1, 1) auf. lösen (1, 1) ruft lösen (2, 2) auf. Da s [2]! = T [2] ist, wird die Suche von lösen (3, 0) neu gestartet. Aab ist jedoch ein Teilstring und überprüft dies niemals oder berücksichtigt diesen Fall ...

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;
}

Dies sollte den Trick tun. Ich habe es in einem Meta-Code ähnlich wie Basic geschrieben.

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

Ich denke, das Hauptproblem ist Ihre for-Schleife innerhalb der else-Anweisung, die dann die Funktion rekursiv aufruft.

Wählen Sie einen Ansatz, entweder Rekursion oder Iteration, aber das Mischen scheint einfach falsch.

Ich würde mit dem iterativen Ansatz gehen.

Ich würde eine leere Liste außerhalb der Funktion erstellen.

Dann ruf an solve.

Versuchen Sie in dieser Funktion diesen Ansatz:

Durchlaufen der Zeichenfolge: Wenn das aktuelle Zeichen nicht der Anfang der Teilsequenz ist, fügen Sie das Zeichen in eine Haltezeichenfolge ein. Dadurch wird eine Zeichenfolge aufgebaut. Wenn die Teilsequenz gestartet wird, fügen Sie diese Zeichen einer anderen Haltezeichenfolge hinzu. Markieren Sie, wie viele Übereinstimmungen Sie mit der Teilsequenz haben. Wenn jedes Zeichen bereits mit der Teilsequenz übereinstimmt, prüfen Sie, ob es mit dem ersten Zeichen übereinstimmt, und ob es mit dem Zeichen an der nächsten zu übereinstimmenden Position übereinstimmt. Wenn es mit der Teilsequenz übereinstimmt, wird alles davor (in der Haltezeichenfolge) in die Liste aufgenommen.

Im Grunde müssen Sie also verfolgen, welche Sequenz möglicherweise gewinnt, und Sie müssen verfolgen, ob sich eine Teilsequenz innerhalb einer anderen Teilsequenz befindet.

Möglicherweise benötigen Sie mehrere Haltezeichenfolgen, implementieren jedoch einen einfachen Ansatz mit zwei Haltezeichenfolgen. Gehen Sie dann verschiedene Beispiele durch und schreiben Sie auf, was in jedem Schritt geschieht, bis Sie feststellen, ob eine weitere Haltezeichenfolge erforderlich ist.

Ich denke, Sie müssen den Y-Teilstring wie einen regulären Ausdruck behandeln und in einen DFA umwandeln. Anschließend leiten Sie die Eingabe durch den DFA und verfolgen, wie lange es her ist, seit Sie eine Übereinstimmung hatten. Es scheint ein lineares Zeitproblem zu sein, vorausgesetzt, die Größe der Eingabe ist viel größer als die Komplexität der übereinstimmenden Zeichenfolge.