Suffix Array

#include <bits/stdc++.h>

int N, C[100005], R[100005], SA[100005], TR[100005], TSA[100005];
using namespace std;

void count_sort(int k)
{
    int sz = max(255,N-1);
    for(int i = 0; i <= sz; i++) C[i] = 0;
    for(int i = 0; i < N; i++) C[R[SA[i]+k]]++;
    int sum = 0;
    for(int i = 0; i <= sz; i++)
    {
        int temp = C[i];
        C[i] = sum;
        sum += temp;
    }
    for(int i = 0; i < N; i++) TSA[C[R[SA[i]+k]]++] = SA[i];
    for(int i = 0; i < N; i++) SA[i] = TSA[i];
}

int main()
{
    string s = "AAAA";
    N = s.length();
    for(int i = 0; i < N; i++) SA[i] = i, R[i] = s[i] - '.';
    for(int k = 1; k < N; k *= 2)
    {
        count_sort(k);
        count_sort(0);
        int rank = 0;
        TR[SA[0]] = 0;
        for(int i = 1; i < N; i++) TR[SA[i]] = R[SA[i]] == R[SA[i-1]] && R[SA[i]+k] == R[SA[i-1]+k] ? rank : ++rank;
        for(int i = 0; i < N; i++) R[i] = TR[i];
    }
    for(int i = 0; i < N; i++) cout << s.substr(SA[i]) << "\n";
}