title: Suffix Array Construction O(N LogN) - Competitive Programming 3 Steven Halim
body: <p>I reading up the book Competitive Programming 3 by Steven Halim and Felix Halim</p>
  
  <p>I'm reading the chapter on Strings.I'm trying to understand the suffix array construction algorithm. I dont understand the radix sort part.       (Although, I understand how radix sort and counting sort works)</p>
  
  <p>Here is the code from the book</p>
  
  <pre><code>#define MAX_N 100010 // second approach: O(n log n)
  char T[MAX_N]; // the input string, up to 100K characters
  int n; // the length of input string
  
  int RA[MAX_N], tempRA[MAX_N]; // rank array and temporary rank array
  int SA[MAX_N], tempSA[MAX_N]; // suffix array and temporary suffix array
  
  int c[MAX_N]; // for counting/radix sort
  
  void countingSort(int k) { // O(n)
  
      int i, sum, maxi = max(300, n); // up to 255 ASCII chars or length of n
      memset(c, 0, sizeof c); // clear frequency table
  
      for (i = 0; i &lt; n; i++){ // count the frequency of each integer rank
          c[i + k &lt; n ? RA[i + k] : 0]++;
      }
      for (i = sum = 0; i &lt; maxi; i++) {
          int t = c[i]; c[i] = sum; sum += t; 
      }
      for (i = 0; i &lt; n; i++){ // shuffle the suffix array if necessary
          tempSA[c[SA[i]+k &lt; n ? RA[SA[i]+k] : 0]++] = SA[i];
      }
      for (i = 0; i &lt; n; i++){ // update the suffix array SA
          SA[i] = tempSA[i];
      }
  }
  
  void constructSA() { // this version can go up to 100000 characters
      int i, k, r;
      for (i = 0; i &lt; n; i++) RA[i] = T[i]; // initial rankings
      for (i = 0; i &lt; n; i++) SA[i] = i; //initial SA: {0, 1, 2, ..., n-1}
  
      for (k = 1; k &lt; n; k &lt;&lt;= 1) { // repeat sorting process log n times
          countingSort(k); //actually radix sort:sort based on the second item
          countingSort(0); // then (stable) sort based on the first item
  
          tempRA[SA[0]] = r = 0; // re-ranking; start from rank r = 0
  
          // compare adjacent suffixes
          for (i = 1; i &lt; n; i++){
              // if same pair =&gt; same rank r; otherwise,increase r
              tempRA[SA[i]] = (RA[SA[i]] == RA[SA[i-1]] &amp;&amp; RA[SA[i]+k] == RA[SA[i-1]+k]) ? r : ++r;           
          }
  
          for (i = 0; i &lt; n; i++){// update the rank array RA
              RA[i] = tempRA[i];
          }
  
          if (RA[SA[n-1]] == n-1) break; // nice optimization trick
      } 
  }
  </code></pre>
  
  <p>Can somebody please explain what is happening the in these lines of the countingSort() function?</p>
  
  <pre><code>for (i = sum = 0; i &lt; maxi; i++) {
      int t = c[i]; c[i] = sum; sum += t; 
  }
  for (i = 0; i &lt; n; i++){ // shuffle the suffix array if necessary
      tempSA[c[SA[i]+k &lt; n ? RA[SA[i]+k] : 0]++] = SA[i];
  }
  for (i = 0; i &lt; n; i++){ // update the suffix array SA
      SA[i] = tempSA[i];
  }
  </code></pre>
  
  <p>Thanks a lot for your valuable time.</p>