Pseudocode mit O(n) Laufzeit Algorithmus

Question

Frage:

Ich muss eine Pseudocode einen Algorithmus implementieren, der für Müster A=a0, a2,...am-1 den Startindex des letzten Vorkommens in einem Text B=b0,b1,...,bn-1 zurückgibt oder -1 wenn Muster im Text nicht vorkommt.

Für A gelte ∀i, j ∈ {0, 1, 2, . . . , m − 1}

Welche Verfahren kann ich nutzen?

Answer 1

Antwort mit KI erzeugt

Antwort auf die Aufgabe:

Um einen Algorithmus mit einer Laufzeit von \(O(n)\) zu erstellen, der den Startindex des letzten Vorkommens des Musters \(A\) in einem Text \(B\) findet oder -1 zurückgibt, falls das Muster nicht vorkommt, können Sie den Knuth-Morris-Pratt (KMP) Algorithmus mit einer kleinen Anpassung nutzen.

Der klassische KMP-Algorithmus ist dafür ausgelegt, das erste Vorkommen eines Musters in einem Text effizient zu finden. Mit einer spezifischen Anpassung kann der Algorithmus jedoch so modifiziert werden, dass er das letzte Vorkommen findet. Dazu speichern wir während der Suche den jeweils aktuellen Fundort des Musters und aktualisieren diesen, bis das Ende des Textes erreicht ist.

Pseudocode mit Anpassungen für das letzte Vorkommen:

1. Berechne das Längenpräfix-Array (LPS) für das Muster \(A\):
- Initialisiere ein Array lps der Länge \(m\) mit 0.
- Durchlaufe das Muster \(A\) und fülle lps basierend auf den Wiederholungen von Präfixen in Suffixen.

2. Suche das Muster \(A\) in \(B\):
- Initialisiere zwei Zeiger: i für den Text \(B\) und j für das Muster \(A\), beide starten bei 0.
- Durchlaufe den Text \(B\). Vergleiche aktuelle Zeichen und bewege i und j entsprechend.
- Wenn ein vollständiges Vorkommen von \(A\) in \(B\) gefunden wird:
- Speichere den aktuellen Index (i - m) als Start des letzten Vorkommens.
- Bewege \(j\) basierend auf dem lps-Array, um nach weiteren Vorkommen zu suchen, ohne den Suchprozess neu zu starten.
- Wenn das Ende von \(B\) erreicht ist und kein Vorkommen gefunden wurde, gebe -1 zurück.
- Andernfalls gebe den gespeicherten Index des letzten Vorkommens zurück.

Pseudocode:

plaintext
Funktion KMP_Suche(Text B, Muster A)
    m = Länge(A)
    n = Länge(B)
    lps = BerechneLPS(A)
    i = 0
    j = 0
    LetztesVorkommen = -1

    Solange i < n
        Wenn A[j] == B[i]
            j++
            i++
        Ende Wenn
        
        Wenn j == m
            LetztesVorkommen = i - j
            j = lps[j - 1]
        Sonst wenn i < n und A[j] != B[i]
            Wenn j != 0
                j = lps[j - 1]
            Sonst
                i = i + 1
            Ende Wenn
        Ende Wenn
    Ende Solange
    
    Rückgabe LetztesVorkommen
Ende Funktion

Funktion BerechneLPS(Muster A)
    Länge = Länge(A)
    lps = Array von Länge mit 0en
    längeDesVorherigenLPS = 0
    i = 1

    Solange i < Länge
        Wenn A[i] == A[längeDesVorherigenLPS]
            längeDesVorherigenLPS++
            lps[i] = längeDesVorherigenLPS
            i++
        Sonst
            Wenn längeDesVorherigenLPS != 0
                längeDesVorherigenLPS = lps[längeDesVorherigenLPS - 1]
            Sonst
                lps[i] = 0
                i++
            Ende Wenn
        Ende Wenn
    Ende Solange
    
    Rückgabe lps
Ende Funktion

*Wichtig*: Die Laufzeit dieses Algorithmus ist \(O(n)\) aufgrund der effizienten Berechnung der lps-Tabelle und des linearen Durchlaufens des Textes, wobei Überprüfungen und Verschiebungen basierend auf dem lps-Wert durchgeführt werden, sodass keine erneute Überprüfung von Zeichen erforderlich ist.