Come velocizzare il calcolo della lunghezza della più lunga sottostringa comune?

Question

Ho due molto grande stringhe e sto cercando di scoprire il loro Longest Common Substring .

Un modo è utilizzare alberi suffisso (dovrebbe avere una buona complessità, anche se un'implementazione complessa), e l'altro è il metodo dinamico programmazione (entrambi riportati sulla pagina di Wikipedia linkato sopra).

Utilizzo di programmazione dinamica

Il problema è che il metodo di programmazione dinamica ha un tempo di esecuzione enorme (complessità è O(n*m), dove n e m sono lunghezze delle due stringhe).

Quello che voglio sapere (prima di saltare per implementare alberi suffisso): E 'possibile velocizzare l'algoritmo se solo voglio sapere la lunghezza della sottostringa comune (e non il comune sottostringa stesso)

Answer 1

Sarà più veloce, in pratica? Sì. Sarà più veloce per quanto riguarda Big-Oh? No. La soluzione di programmazione dinamica è sempre O (n * m).

Il problema che si potrebbe incorrere in con alberi suffisso è che si scambi scansione tempo lineare dell'albero suffisso per una pena enorme nello spazio. alberi suffisso sono generalmente molto più grandi rispetto alla tabella avresti bisogno di implementare una versione programmazione dinamica dell'algoritmo. A seconda della lunghezza delle corde, è del tutto possibile che la programmazione dinamica sarà più veloce.

Buona fortuna:)

Answer 2

Questi farlo correre più veloce, anche se sarà ancora O(nm).

Un'ottimizzazione è nello spazio (che si potrebbe risparmiare un po 'di tempo di allocazione) è meno di notare che LCSuff dipende solo dalla riga precedente - quindi se vi interessa soltanto la lunghezza, è possibile ottimizzare lo spazio O(nm) verso il basso per O(min(n,m)) <. / p>

L'idea è quella di mantenere solo due file -. La riga corrente che si sta elaborando, e la riga precedente appena elaborato, e gettare via il resto

Answer 3

Ecco un semplice algoritmo che può finiture in O ((m + n) * log (m + n)), e molto più facile da implementare rispetto a algoritmo albero suffisso che è O (m + n) tempo di esecuzione.

lasciare che venga avviato lunghezza min comune (minL) = 0, e massima lunghezza comune (Maxl) = min (m + n) +1.

1. if (minL == maxL - 1), the algorithm finished with common len = minL.

2. let L = (minL + maxL)/2

3. hash every substring of length L in S, with key = hash, val = startIndex.

4. hash every substring of length L in T, with key = hash, val = startIndex. check if any hash collision in to hashes. if yes. check whether whether they are really common substring. 

5. if there're really common substring of length L, set minL = L, otherwise set maxL = L. goto 1.

Il problema che rimane è come hash tutte stringa di lunghezza L in tempo O (n). È possibile utilizzare una formula polinomiale come segue:

Hash(string s, offset i, length L) = s[i] * p^(L-1) + s[i+1] * p^(L-2) + ... + s[i+L-2] * p + s[i+L-1]; choose any constant prime number p.

then Hash(s, i+1, L) = Hash(s, i, L) * p - s[i] * p^L + s[i+L];

Answer 4

di Myer vettore di bit algoritmo ti può aiutare. Funziona utilizzando la manipolazione bit ed è un approccio molto più veloce.