Suffix Array

struct SuffixArray{
  vector<char> s;
  vector<int> p, num, pcur, lcp;
  vector<vector<int> > c;
  int classesNum, n;
  int MAXN, ALPH, MAXLOG;
  SuffixArray(int MAXN, int ALPH){
    this->MAXN = MAXN;
    this->ALPH = ALPH;
    MAXLOG = log2(MAXN) + 1;
    p.resize(MAXN);
    c.resize(MAXN);
    classesNum = 0;
    pcur.resize(MAXN);
    s.resize(MAXN);
    num.resize(MAXN);
    lcp.resize(MAXN);
    for(int j = 0; j < MAXN; ++j)
      c[j].resize(MAXLOG);
    n = 0;
  }
  void buildSuffixArray() {
      n++;

      for (int i = 0; i < n; i++) 
          num[s[i]]++;    

      for (int i = 1; i < ALPH; i++)
          num[i] += num[i - 1];

      for (int i = 0; i < n; i++) {
          p[num[s[i]] - 1] = i;
          num[s[i]]--;
      }

      c[p[0]][0] = 1;
      classesNum = 1;
      for (int i = 1; i < n; i++) {
          if (s[p[i]] != s[p[i - 1]])
              classesNum++;
          c[p[i]][0] = classesNum;
      }

      for (int i = 1; ; i++) {
          
          int half = (1 << (i - 1));      
          
          for (int j = 0; j < n; j++) {
              pcur[j] = p[j] - half;
              if (pcur[j] < 0)
                  pcur[j] += n;   
          }

          for (int j = 1; j <= classesNum; j++)
              num[j] = 0;

          for (int j = 0; j < n; j++) 
              num[c[pcur[j]][i - 1]]++;
          for (int j = 2; j <= classesNum; j++)
              num[j] += num[j - 1];
          
          for (int j = n - 1; j >= 0; j--) {
              p[num[c[pcur[j]][i - 1]] - 1] = pcur[j];
              num[c[pcur[j]][i - 1]]--;
          }

            c[p[0]][i] = 1;
            classesNum = 1;

            for (int j = 1; j < n; j++) {
                int p1 = (p[j] + half) % n, p2 = (p[j - 1] + half) % n;
                if (c[p[j]][i - 1] != c[p[j - 1]][i - 1] || c[p1][i - 1] != c[p2][i - 1])
                    classesNum++;
                c[p[j]][i] = classesNum;
            }

            if ((1 << i) >= n)
                break;
        }

        for (int i = 0; i < n; i++)
            p[i] = p[i + 1];
        n--;
  }
};