Algoritmul Kasai
Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de
versiunea revizuită la 6 octombrie 2016; verificările necesită
4 modificări .
Algoritmul Kasai ( Arimura - Arikawa - Kasai - Lee - Paka) este un algoritm care găsește în timp liniar lungimile celor mai lungi prefixe comune ( engleză lcp, longest common prefix ) pentru toate perechile de sufixe ale unui șir dat care sunt adiacente în ordine lexicografică (adică pentru toate elementele de matrice sufixe ). Intrarea algoritmului este șirul în sine și matricea de sufixe, rezultatul este o matrice de lungimi ale celor mai mari prefixe comune.
clasa publică Kasai {
// în elemente sufArray (s.length() + 1) - inclusiv sufix gol
public static int [] solve ( String s , String [] sufArray ) {
int pos [] = new int [ s . lungime () + 1 ] ;
pentru ( int i = 0 ; i <= s . lungime (); i ++ ) {
pos [ i ] = s . lungime () - sufArray [ i ] . lungime ( ) + 1 } rang int [] = int nou [ s . lungime () + 1 ] ; pentru ( int i = 0 ; i <= s . lungime (); i ++ ) { rang [ pos [ i ]] = i ; } int ans [] = new int [ s . lungime () + 1 ] ; int h = 0 ; pentru ( int i = 1 ; i <= s . lungime (); i ++ ) { if ( rang [ i ] > 1 ) { int k = pos [ rang [ i ] - 1 ] ; în timp ce ((( i + h - 1 ) != s . lungime ()) && (( k + h - 1 ) != s . lungime ()) && ( s . charAt ( i + h - 1 ) == s .charAt ( k + h - 1 ) )) h ++ ; ans [ rang [ i ]] = h ; dacă ( h > 0 ) h -- ; } } return ans ; // ans[i + 1] = cel mai lung prefix comun al sufArray[i] și sufArray[i - 1] } }
Implementare în C++
// Această implementare presupune că există un caracter la sfârșitul textului care este diferit de toate celelalte ("caracter terminal").
// Rețineți că implementarea algoritmului este vizibil diferită de cea precedentă.
void solve ( const std :: string & text , const std :: vector < int >& pos , std :: vector < int >& lcp )
{
int n = text . lungime ();
std :: vector < int > rank ( n );
pentru ( int i = 0 ; i < n ; ++ i ) rang [ pos [ i ]] = i ;
pentru ( int i = 0 , k = 0 ; i < n ; ++ i )
{
dacă ( k > 0 ) k -- ;
dacă ( rang [ i ] == n - 1 )
{ lcp [ n - 1 ] = -1 , k = 0 ; continua ;
}
int j = pos [ rang [ i ] + 1 ];
while ( max ( i + k , j + k ) < text . length () && text [ i + k ] == text [ j + k ]) k ++ ;
lcp [ rang [ i ]] = k ;
}
// lcp[x] - cel mai lung prefix comun al sufixelor pos[x] și pos[x + 1]
}
Note
Literatură
- Kasai, Toru și Lee, Gunho și Arimura, Hiroki și Arikawa, Setsuo și Park, Kunsoo (2001). „Calcul liniar în timp cu cel mai lung prefix comun în matrice de sufixe și aplicațiile sale” . Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching . CPM'01. Springer-Verlag. pp. 181-192. Kasai:2001:LLC:647820.736222 . Accesat 2013-12-06 .
- Guigo, R. și Gusfield, D. Algoritmi în bioinformatică: al doilea atelier internațional, WABI 2002, Roma, Italia, 17-21 septembrie 2002, Proceedings. - Springer, 2002. - P. 453-455. — ISBN 9783540442110 .