Mam następujący kod: http://pastebin.com/0cvGkZMT autorstwa Pana Marka Weissa (nie chcę go tu wklejać, gdyż zajmuje sporo miejsca). Ogólnie jest on dla mnie zrozumiały w większości jednakże nurtuje mnie fragment dotyczący sortowania pozycyjnego, a dokładniej ten fragment kodu:
private static int assignNames( int [ ] s, int [ ] s12, int [ ] SA12,
int n0, int n12, int K )
{
// radix sort the new character trios
radixPass( s12 , SA12, s, 2, n12, K );
radixPass( SA12, s12 , s, 1, n12, K );
radixPass( s12 , SA12, s, 0, n12, K );
// find lexicographic names of triples
int name = 0;
int c0 = -1, c1 = -1, c2 = -1;
for( int i = 0; i < n12; i++ )
{
if( s[ SA12[ i ] ] != c0 || s[ SA12[ i ] + 1 ] != c1
|| s[ SA12[ i ] + 2 ] != c2 )
{
name++;
c0 = s[ SA12[ i ] ];
c1 = s[ SA12[ i ] + 1 ];
c2 = s[ SA12[ i ] + 2 ];
}
if( SA12[ i ] % 3 == 1 )
s12[ SA12[ i ] / 3 ] = name;
else
s12[ SA12[ i ] / 3 + n0 ] = name;
}
return name;
}
// stably sort in[0..n-1] with indices into s that has keys in 0..K
// into out[0..n-1]; sort is relative to offset into s
// uses counting radix sort
private static void radixPass( int [ ] in, int [ ] out, int [ ] s, int offset,
int n, int K )
{
int [ ] count = new int[ K + 2 ]; // counter array
for( int i = 0; i < n; i++ )
count[ s[ in[ i ] + offset ] + 1 ]++; // count occurences
for( int i = 1; i <= K + 1; i++ ) // compute exclusive sums
count[ i ] += count[ i - 1 ];
for( int i = 0; i < n; i++ )
out[ count[ s[ in[ i ] + offset ] ]++ ] = in[ i ]; // sort
}
// stably sort in[0..n-1] with indices into s that has keys in 0..K
// into out[0..n-1]
// uses counting radix sort
private static void radixPass( int [ ] in, int [ ] out, int [ ] s, int n, int K )
{
radixPass( in, out, s, 0, n, K );
}
Wiem na czym polega sortowanie pozycyjne ale w jaki sposób tutaj to sortowanie działa? Mógłby ktoś łopatologicznie wyjaśnić? Chciałbym zmienić nieco to sortowanie tak, by w przypadku gdy trafiają się takie dwa sufiksy słowa, że jeden z nich z zawiera się w drugim (np. ababa i aba), to żeby wtedy wcześniejszym był ten dłuższy, a nie ten krótszy jak jest to normalnie w porządku leksykograficznym. Właśnie dlatego potrzebuję dokładniej zrozumieć przytoczony powyżej fragment kodu.
Z góry dzięki.