#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 2012 , LEN = 100111;

char str[LEN];

struct SuffixArray {
    int wa[LEN] , wb[LEN] , wv[LEN] , ws[LEN];
    int n , m , r[LEN] , sa[LEN] , rank[LEN] , h[LEN];
    void init(char *str) {
        n = strlen(str);
        for(int i = 0 ; i < n ; i++) r[i] = str[i] - 'a' + 1;
        r[n] = 0 , m = 27; // change
    }
    inline int cmp(int *y , int a , int b , int l) {
        return y[a] == y[b] && y[a+l] == y[b+l];
    }
    void get_sa(int n) {
        int i , j , p , *x = wa , *y = wb , *t;
        for(i = 0 ; i < m ; i++) ws[i] = 0;
        for(i = 0 ; i < n ; i++) ws[x[i] = r[i]]++;
        for(i = 1 ; i < m ; i++) ws[i] += ws[i-1];
        for(j = 1 , p = 1 ; p < n ; j <<= 1 , m = p) {
            for(p = 0 , i = n - j ; i < n ; i++) y[p++] = i;
            for(i = 0 ; i < n ; i++) if(sa[i] >= j) y[p++] = sa[i] - j;
            for(i =  0 ; i < m ; i++) ws[i] = 0;
            for(i = 0 ; i < n ; i++) ws[wv[i] = x[y[i]]]++;
            for(i = 1 ; i < m ; i++) ws[i] += ws[i-1];
            for(i = n - 1 ; i >= 0 ; i--) sa[--ws[wv[i]]] = y[i];
            swap(x , y) , p = 1 , x[sa[0]] = 0;
            for(i = 1 ; i < n ; i++)
                x[sa[i]] = cmp(y , sa[i-1] , sa[i] , j) ? p - 1 : p++;
        }
    }
    void get_h() {
        int i , j , k = 0;
        for(i = 1 ; i <= n ; i++) rank[sa[i]] = i;
        for(i = 0 ; i < n ; h[rank[i++]] = k)
            for(k ? k--:0 , j = sa[rank[i]-1] ; r[i+k] == r[j+k] ; k++);
    }
    void out() {
        get_sa(n + 1);
        puts("hehe");
        get_h();
        puts("rank array:");
        for(int i = 0 ; i < n ; i++) printf("%d " , rank[i]);
        puts("\nsa array");
        for(int i = 1 ; i <= n ; i++) printf("%d " , sa[i]);
        puts("\nheight array");
        for(int i = 1 ; i <= n ; i++) printf("%d " , h[i]);
        puts("");
    }
}sf;

int main() {
    scanf("%s" , str);
    sf.init(str);
    sf.out();
    return 0;
}