Kasai algoritmus
Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2016. október 6-án felülvizsgált
verziótól ; az ellenőrzések 4 szerkesztést igényelnek .
A Kasai-algoritmus ( Arimura - Arikawa - Kasai - Lee - Paka) egy olyan algoritmus , amely lineáris időben megkeresi a leghosszabb közös előtagok ( angolul lcp, leghosszabb közös előtag ) hosszát egy adott karakterlánc összes olyan utótagpárjához, amelyek szomszédosak lexikográfiai sorrend (vagyis az összes szomszédos utótag tömb ). Az algoritmus bemenete maga a karakterlánc és az utótag tömb, a kimenet a legnagyobb közös előtagok hosszúságú
tömbje .
public class Kasai {
// sufArray-ben (s.length() + 1) elemek - beleértve az üres utótagot
public static int [] solve ( String s , String [] sufArray ) {
int pos [] = new int [ s . hossz () + 1 ] ;
for ( int i = 0 ; i <= s . hosszúság (); i ++ ) {
poz [ i ] = s . hossza () - sufArray [ i ] . hossza ( ) + 1 } int rang [] = új int [ s . hossz () + 1 ] ; for ( int i = 0 ; i <= s . hossz (); i ++ ) { rang [ poz [ i ]] = i ; } int ans [] = új int [ s . hossz () + 1 ] ; int h = 0 ; for ( int i = 1 ; i <= s . long (); i ++ ) { if ( rang [ i ] > 1 ) { int k = pos [ rang [ i ] - 1 ] ; while ((( i + h - 1 ) != s . hossz ()) && (( k + h - 1 ) != s . hossz ()) && ( s . charAt ( i + h - 1 ) == s .charAt ( k + h - 1 ) )) h ++ ; ans [ rang [ i ]] = h ; ha ( h > 0 ) h -- ; } } return ans ; // ans[i + 1] = a sufArray[i] és a sufArray[i - 1] leghosszabb közös előtagja } }
// Ez a megvalósítás feltételezi, hogy a szöveg végén van egy karakter, amely különbözik az összes többitől ("terminálkarakter").
// Megjegyezzük, hogy az algoritmus megvalósítása észrevehetően eltér az előzőtől.
void megold ( const std :: string & text , const std :: vektor < int >& pos , std :: vektor < int >& lcp )
{
int n = szöveg . hossz ();
std :: vektor < int > rang ( n );
for ( int i = 0 ; i < n ; ++ i ) rang [ pos [ i ]] = i ;
for ( int i = 0 , k = 0 ; i < n ; ++ i )
{
ha ( k > 0 ) k -- ;
if ( rang [ i ] == n - 1 )
{ lcp [ n - 1 ] = -1 , k = 0 ; tovább ;
}
int j = pos [ rang [ i ] + 1 ];
while ( max ( i + k , j + k ) < szöveg . hossz ( ) && szöveg [ i + k ] == szöveg [ j + k ]) k ++ ;
lcp [ rang [ i ]] = k ;
}
// lcp[x] - a pos[x] és pos[x + 1] utótagok leghosszabb közös előtagja
}
Jegyzetek
Irodalom
- Kasai, Toru és Lee, Gunho és Arimura, Hiroki és Arikawa, Setsuo és Park, Kunsoo (2001). „Lineáris idejű leghosszabb közös előtag számítása utótagtömbökben és alkalmazásaiban” . Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching . CPM'01. Springer-Verlag. pp. 181-192. Kasai:2001:LLC:647820.736222 . Letöltve: 2013-12-06 .
- Guigo, R. és Gusfield, D. Algorithms in Bioinformatics: Second International Workshop, WABI 2002, Róma, Olaszország, 2002. szeptember 17-21., Proceedings. - Springer, 2002. - P. 453-455. — ISBN 9783540442110 .