Qual è la complessità peggiore per KMP quando l'obiettivo è trovare tutte le occorrenze di una determinata stringa?

Question

Vorrei anche sapere quale algoritmo ha il peggior caso la complessità di tutti per trovare tutte le occorrenze di una stringa in un altro. Sembra che l'algoritmo di Boyer-Moore abbia una complessità temporale lineare.

Answer 1

L'algoritmo KMP ha una complessità lineare per trovare tutte le occorrenze di un modello in una stringa, come l'algoritmo Boyer-Moore¹. Se si tenta di trovare un modello come "aaaaaa" in una stringa come "aaaaaaaaa", una volta che hai la prima partita completa,

aaaaaaaaa 
aaaaaa 
aaaaaa 
    ^

tabella confine contiene le informazioni che la prossima partita più lunga possibile (corrispondente al bordo più largo del pattern) di un prefisso del pattern è solo un carattere breve (una corrispondenza completa equivale a una mancata corrispondenza oltre la fine del pattern in questo senso). Così il modello viene spostato di un luogo ulteriore, e dato dalla tabella confine è noto che tutti i caratteri del modello eccetto forse l'ultima partita, il successivo confronto è tra l'ultimo carattere del modello e il carattere di testo allineato. In questo caso particolare (trovare le occorrenze di una ^m in un ⁿ), che è il caso peggiore per l'algoritmo di corrispondenza ingenuo, l'algoritmo KMP confronta ogni carattere di testo esattamente una volta.

In ogni fase, almeno uno dei

• la posizione del carattere di testo rispetto
• la posizione del primo carattere del modello rispetto al testo

aumenta, e nessuno dei due diminuisce mai. La posizione del carattere di testo rispetto può aumentare al massimo length(text)-1 volte, la posizione del primo carattere modello può aumentare al massimo length(text) - length(pattern) volte, quindi l'algoritmo richiede al massimo 2*length(text) - length(pattern) - 1 passi.

La preelaborazione (costruzione del tavolo confine) batte al massimo 2*length(pattern) passi, così la complessità generale è O (m + n) e vengono eseguiti altri m + 2*n passaggi se m è la lunghezza del pattern e n la lunghezza il testo.

¹ Si noti che l'algoritmo di Boyer-Moore come comunemente presentato ha un caso peggiore complessità O (m * n) per i modelli di periodici e testi come un ^m e ⁿ se sono necessarie tutte le partite, perché dopo una corrispondenza completa,

aaaaaaaaa 
aaaaaa 
aaaaaa 
    ^
    <- <- 
^ 

l'intero modello viene ricontestualizzato. Per evitare ciò, è necessario ricordare per quanto tempo un prefisso del modello corrisponde ancora dopo il turno successivo a una corrispondenza completa e solo confrontare i nuovi caratteri.

Answer 2

Potete contare funzione PI per una stringa in O(length). KMP costruisce una stringa speciale che ha lunghezza n+m+1, e conta funzione Pi su di esso, così in ogni caso complessità sarà O(n+m+1)=O(n+m)

Answer 3

C'è un lungo articolo KMP a http://en.wikipedia.org/wiki/Knuth-morris-pratt che termina con dire

Poiché le due porzioni dell'algoritmo hanno, rispettivamente, complessità di O (k) e O (n), la complessità dell'algoritmo complessivo è O (n + k).

queste complessità sono gli stessi, indipendentemente dal numero di schemi ripetitivi sono in W o S. (fine citazione)

Quindi il costo totale di una ricerca KMP è lineare nel numero di caratteri della stringa e modello . Penso che questo vale anche se hai bisogno di trovare più occorrenze del pattern nella stringa - e se no, basti pensare alla ricerca di patternQ, dove Q è un personaggio che non si verifica nel testo, e annotando dove gli spettacoli di stato KMP che ha abbinato tutto alla Q.