Calcolo della seconda tabella (errata corrispondenza) nell'algoritmo di ricerca delle stringhe di Boyer-Moore

Question

Affinché l'algoritmo di Boyer-Moore sia lineare nel caso peggiore, il calcolo della tabella di errata corrispondenza deve essere O (m). Tuttavia, un'implementazione ingenua passerebbe attraverso tutti i suffissi O (m) e tutte le posizioni in cui quel suffisso potrebbe andare e verificare l'uguaglianza ... che è O (m ³ )!

Di seguito è riportata l'implementazione ingenua di algoritmo di creazione di tabelle . Quindi questa domanda diventa: Come posso migliorare il tempo di esecuzione di questo algoritmo su O (m)?

def find(s, sub, no):
    n = len(s)
    m = len(sub)

    for i in range(n, 0, -1):
        if s[max(i-m, 0): i] == sub[max(0, m-i):] and \
            (i-m < 1 or s[i-m-1] != no):
            return n-i

    return n

def table(s):
    m = len(s)
    b = [0]*m

    for i in range(m):
        b[i] = find(s, s[m-i:], s[m-i-1])

    return b

print(table('anpanman'))

Per mettere a riposo le menti, non si tratta di compiti a casa. Aggiungerò delle revisioni quando qualcuno pubblicherà idee per miglioramenti.

Answer 1

Il codice sotto " Preelaborazione per l'euristica del buon suffisso " su questa pagina crea la tabella del suffisso buono in Puntuale. Spiega anche come funziona il codice.