private int[] determineAll_Buckets_Sarray(int q) {

        int strLen = length;
        int alphabetSize = alphabet.size;
        int numberBuckets = kbs_power_Ulong(alphabetSize, q);
        int[] buckets = new int[numberBuckets + 1];
        for (int i = 0; i < q; i++) {
            seq[start + length + i] = alphabet.charArray[0];
        }
        for (int i = 0; i < KBS_STRING_EXTENSION_SIZE - q; i++) {
            seq[start + length + i + q] = 0;
        }
        /* computation of first hashvalue */
        int[] alphaMap = alphabet.alphaMapping;
        int mappedUcharArray = 0;
        int hashCode = 0;
        int tempPower = 1;
        int i;
        for (i = q - 1; i >= 0; i--) {
            hashCode += (seq[start + mappedUcharArray + i] = alphaMap[seq[start
                + mappedUcharArray + i]])
                * tempPower;
            tempPower *= alphabetSize;
        }
        int firstHashCode = hashCode;
        /* computation of the size of buckets */
        int tempModulo = kbs_power_Ulong(alphabetSize, q - 1);
        mappedUcharArray += q;
        buckets[hashCode]++;
        int j;
        for (j = 1; j < strLen; j++) {
            hashCode -= (seq[start + mappedUcharArray - q]) * tempModulo;
            hashCode *= alphabetSize;
            hashCode += seq[start + mappedUcharArray] = alphaMap[seq[start
                + mappedUcharArray]];
            mappedUcharArray++;
            buckets[hashCode]++;
        }
        /* update the alphabet for mapped string */
        for (j = 0; j < alphabetSize; j++) {
            alphabet.charFreq[j] = alphabet.charFreq[alphabet.charArray[j]];
            alphabet.charArray[j] = j;
            alphaMap[j] = j;
        }
        for (; j < KBS_MAX_ALPHABET_SIZE; j++) {
            alphaMap[j] = -1;
        }

        this.suffixArray = new int[strLen + 1];
        /* computation of the bucket pointers, pointers into the suffix array */
        for (j = 1; j <= numberBuckets; j++) {
            buckets[j] = buckets[j - 1] + buckets[j];
        }

        /* computation of the suffix array (buckets that are copied later are left out) */
        int[] charRank = getCharWeightedRank_Alphabet(buckets, q);

        mappedUcharArray = q;
        hashCode = firstHashCode;
        for (j = 0; j < strLen - 1; j++) {
            int c1;
            buckets[hashCode]--;
            if ((c1 = charRank[seq[start + mappedUcharArray - q]]) < charRank[seq[start
                + mappedUcharArray + 1 - q]]
                && c1 <= charRank[seq[start + mappedUcharArray + 2 - q]]) suffixArray[buckets[hashCode]] = j;
            hashCode -= (seq[start + mappedUcharArray - q]) * tempModulo;
            hashCode *= alphabetSize;
            hashCode += seq[start + mappedUcharArray];
            mappedUcharArray++;
        }

        buckets[hashCode]--;
        suffixArray[buckets[hashCode]] = strLen - 1;

        buckets[numberBuckets] = strLen;
        return buckets;
    }
private int [ ] determineAll_Buckets_Sarray ( int q ) { int strLen = length ; int alphabetSize = alphabet . size ; int numberBuckets = kbs_power_Ulong ( alphabetSize , q ) ; int [ ] buckets = new int [ numberBuckets + 1 ] ; for ( int i = 0 ; i < q ; i ++ ) { seq [ start + length + i ] = alphabet . charArray [ 0 ] ; } for ( int i = 0 ; i < KBS_STRING_EXTENSION_SIZE - q ; i ++ ) { seq [ start + length + i + q ] = 0 ; } int [ ] alphaMap = alphabet . alphaMapping ; int mappedUcharArray = 0 ; int hashCode = 0 ; int tempPower = 1 ; int i ; for ( i = q - 1 ; i >= 0 ; i -- ) { hashCode += ( seq [ start + mappedUcharArray + i ] = alphaMap [ seq [ start + mappedUcharArray + i ] ] ) * tempPower ; tempPower *= alphabetSize ; } int firstHashCode = hashCode ; int tempModulo = kbs_power_Ulong ( alphabetSize , q - 1 ) ; mappedUcharArray += q ; buckets [ hashCode ] ++ ; int j ; for ( j = 1 ; j < strLen ; j ++ ) { hashCode -= ( seq [ start + mappedUcharArray - q ] ) * tempModulo ; hashCode *= alphabetSize ; hashCode += seq [ start + mappedUcharArray ] = alphaMap [ seq [ start + mappedUcharArray ] ] ; mappedUcharArray ++ ; buckets [ hashCode ] ++ ; } for ( j = 0 ; j < alphabetSize ; j ++ ) { alphabet . charFreq [ j ] = alphabet . charFreq [ alphabet . charArray [ j ] ] ; alphabet . charArray [ j ] = j ; alphaMap [ j ] = j ; } for ( ; j < KBS_MAX_ALPHABET_SIZE ; j ++ ) { alphaMap [ j ] = - 1 ; } this . suffixArray = new int [ strLen + 1 ] ; for ( j = 1 ; j <= numberBuckets ; j ++ ) { buckets [ j ] = buckets [ j - 1 ] + buckets [ j ] ; } int [ ] charRank = getCharWeightedRank_Alphabet ( buckets , q ) ; mappedUcharArray = q ; hashCode = firstHashCode ; for ( j = 0 ; j < strLen - 1 ; j ++ ) { int c1 ; buckets [ hashCode ] -- ; if ( ( c1 = charRank [ seq [ start + mappedUcharArray - q ] ] ) < charRank [ seq [ start + mappedUcharArray + 1 - q ] ] && c1 <= charRank [ seq [ start + mappedUcharArray + 2 - q ] ] ) suffixArray [ buckets [ hashCode ] ] = j ; hashCode -= ( seq [ start + mappedUcharArray - q ] ) * tempModulo ; hashCode *= alphabetSize ; hashCode += seq [ start + mappedUcharArray ] ; mappedUcharArray ++ ; } buckets [ hashCode ] -- ; suffixArray [ buckets [ hashCode ] ] = strLen - 1 ; buckets [ numberBuckets ] = strLen ; return buckets ; }
Constructs all buckets w.r.t. q-gram size and the up to prefix q sorted suffix
array. Call determine_Buckets_Sarray(const Kbs_Ustring *const ustring, register
const Kbs_Ulong q, Kbs_Ulong **suffixArrayPtr) instead

@param q size of q-gram.
@return Buckets containing pointers into the suffix array.
@see #determine_Buckets_Sarray_Sptrmap(int)