Kasai algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 6. října 2016; kontroly vyžadují 4 úpravy .

Algoritmus Kasai ( Arimura - Arikawa - Kasai - Lee - Paka)  je algoritmus , který v lineárním čase zjišťuje délky nejdelších společných předpon ( anglicky  lcp, longest common prefix ) pro všechny dvojice přípon daného řetězce, které sousedí v lexikografické pořadí (to znamená pro všechny sousední prvky pole přípon ). Vstupem algoritmu je samotný řetězec a pole přípon, výstupem pole délek největších společných prefixů.

Java implementace algoritmu

veřejná třída Kasai { // v prvcích sufArray (s.length() + 1) - včetně prázdné přípony public static int [] solve ( String s , String [] sufArray ) { int pos [] = new int [ s . délka () + 1 ] ; for ( int i = 0 ; i <= s . délka (); i ++ ) { pos [ i ] = s . délka () - sufArray [ i ] . délka ( ) + 1 } int hodnost [] = new int [ s . délka () + 1 ] ; for ( int i = 0 ; i <= s . délka (); i ++ ) { pořadí [ pos [ i ]] = i ; } int ans [] = new int [ s . délka () + 1 ] ; int h = 0 ; for ( int i = 1 ; i <= s . délka (); i ++ ) { if ( pořadí [ i ] > 1 ) { int k = pos [ pořadí [ i ] - 1 ] ; while ((( i + h - 1 ) != s . délka ()) && (( k + h - 1 ) != s . délka ()) && ( s . charAt ( i + h - 1 ) == s .charAt ( k + h - 1 ) )) h ++ ; ans [ pořadí [ i ]] = h ; if ( h > 0 ) h -- ; } } return ans ; // ans[i + 1] = nejdelší společná předpona sufArray[i] a sufArray[i - 1] } }

Implementace v C++

// Tato implementace předpokládá, že na konci textu je znak, který se liší od všech ostatních ("terminální znak"). // Všimněte si, že implementace algoritmu se výrazně liší od předchozího. void solve ( const std :: string & text , const std :: vector < int >& pos , std :: vector < int >& lcp ) { int n = text . délka (); std :: vector < int > rank ( n ); for ( int i = 0 ; i < n ; ++ i ) pořadí [ pos [ i ]] = i ; for ( int i = 0 , k = 0 ; i < n ; ++ i ) { if ( k > 0 ) k -- ; if ( pořadí [ i ] == n - 1 ) { lcp [ n - 1 ] = -1 , k = 0 ; pokračovat ; } int j = pos [ pořadí [ i ] + 1 ]; while ( max ( i + k , j + k ) < text . délka () && text [ i + k ] == text [ j + k ]) k ++ ; lcp [ pořadí [ i ]] = k ; } // lcp[x] - nejdelší společná předpona přípon pos[x] a pos[x + 1] }

Poznámky

Literatura

  • Kasai, Toru a Lee, Gunho a Arimura, Hiroki a Arikawa, Setsuo a Park, Kunsoo (2001). „Výpočet nejdelší společné předpony v lineárním čase v polích přípon a jejich aplikacích“ . Sborník příspěvků z 12. výročního sympozia o kombinatorickém párování vzorů . CPM'01. Springer-Verlag. str. 181-192. Kasai:2001:LLC:647820.736222 . Staženo 2013-12-06 .
  • Guigo, R. a Gusfield, D. Algorithms in Bioinformatics: Second International Workshop, WABI 2002, Řím, Itálie, 17.-21. září 2002, Proceedings. - Springer, 2002. - S. 453-455. — ISBN 9783540442110 .