4

I've coded a Suffix Array implementation and discovered an issue in my implementation. Concretely I've outputted the first few suffix array ranks RA[0..7] of this string(length = 10^5) and had the following output:

80994
84360
87854
91517
95320
99277
83068

But the correct one had to be (everything shifted by 23):

81017
84383
87877
91540
95343
99300
83091

I know two ways how to fix it, but I don't know why it worked.

The first way was adding S[N++] = '$'; to the top of the buildSA() function (then the output was 1 less than the correct one, but it doesn't matter)

I also found another solution by decreasing the MAX_N constant to 1e5 + 10!

This is so much magic for me and I really need to know why this bug happened because I don't want to have this bug again.

#include <cstdio>
#include <cstring>
#include <algorithm>
using std::max;
const int MAX_N = 2e5 + 10;
int SA[MAX_N];   // The ith element is the index of the suffix
int RA[MAX_N];   // The rank of the suffix at i
int tmp[MAX_N];  // A temporary array
int B[MAX_N];    // An array for the buckets
int N;
char S[MAX_N];

void bucketSort(int k){
  int i, m = max(256, N);
  for(i = 0; i < m; i++)
    B[i] = 0;
  for(i = 0; i < N; i++)
    B[i + k < N ? RA[i + k] : 0] ++;
  for(i = 1; i < m; i++)
    B[i] += B[i - 1];
  for(i = N - 1; i >= 0; i--)
    tmp[--B[SA[i] + k < N ? RA[SA[i] + k] : 0]] = SA[i];
  for(i = 0; i < N; i++)
    SA[i] = tmp[i];
}

void buildSA(){
  for(int i = 0; i < N; i++){
    SA[i] = i;
    RA[i] = S[i];
  }
  for(int k = 1; k < N; k <<= 1){
    bucketSort(k);
    bucketSort(0);
    int norder = 0;
    tmp[SA[0]] = 0;
    for(int i = 1; i < N; i++){
      if(RA[SA[i]] == RA[SA[i - 1]] && RA[SA[i] + k] == RA[SA[i - 1] + k])
      {} else norder++;
      tmp[SA[i]] = norder;
    }
    for(int i = 0; i < N; i++)
      RA[i] = tmp[i];
    if(norder == N)
      break;
  }
}

void printSA(){
  for(int i = 0; i < N; i++){
    printf("%d: %s\n", SA[i], S + SA[i]);
  }
}

int main(){
  scanf("%s", S);
  N = strlen(S);
  buildSA();
  for(int i = 0; i < 7; i++){
    printf("%d\n",RA[i]);
  }
  return 0;
}
7
  • 2
    I don't have a problem with being asked to fing bugs (some SOers do), but you have to make an effort by finding a smallest possible input that triggers it. Jun 18, 2014 at 15:27
  • (Looking for a small input that triggers the bug is one of the first things you should do in the process of trying to fix it yourself.) Jun 18, 2014 at 15:29
  • random testing helps find a small problematic input.
    – Niklas B.
    Jun 18, 2014 at 15:36
  • I've done it already and ran the test generator for like two hours...
    – Gary Ye
    Jun 18, 2014 at 15:50
  • 1
    The key to understanding why a bug happens is to understand the algorithm you are writing (i.e. you're not just copying someone elses code). If you don't understand your algorithm, and it appears to you to be "magic", then understanding how to fix it is going to be extremely difficult, and is going to typically involve making semi-random changes until you hit on something that seems to "work", at least until it doesn't, and just perpetuates the perspective of it being "magic"...
    – twalberg
    Jun 18, 2014 at 16:25

2 Answers 2

1

In the following line:
if(RA[SA[i]] == RA[SA[i - 1]] && RA[SA[i] + k] == RA[SA[i - 1] + k])
SA[i] + k can be >=N(the same is for SA[i - 1] + k).
It should be (SA[i] + k) % Ninstead.

1
  • That's true. I verified this by using a very simple testcase (I couldn't generate randomly...) like: abab The resulting suffix array was 0: abab 2: ab 3: b 1: bab which is clearly wrong.
    – Gary Ye
    Jun 18, 2014 at 18:28
0

I think I got it after many wasted hours. Sometimes the littlest mistakes can literally result to wrong answers.

The "bad" code line is:

if(RA[SA[i]] == RA[SA[i - 1]] && RA[SA[i] + k] == RA[SA[i - 1] + k])
      {} else norder++;

I verified this by using a very simple testcase (I couldn't generate randomly...) like:

abab

The resulting suffix array was

0: abab
2: ab
3: b
1: bab

which is clearly wrong.

At step k = 2, if we are comparing two suffixes like ab and abab then, we realize that they have the same rank, since their first k = 2 characters match. ab is suffix #2, by adding k = 2, we are out of range.

I've often coded it like this because I've always appended an auxiliary character (e.g. '$') to the end. If I don't put such a character (like in my case), SA[i] + k could actually be >= N and this code crashes.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.