//String quick sort
#include <iostream>
#include <stdio.h>
#define MAX_N 6
#define SWAP(a, b) do { a ^= b; b ^= a; a ^= b; } while ( 0 )
using namespace std;
inline int my_strlen(const char* str){int n=0;for(n=0;str[n]!='\0';n++);return n;}
int my_strcmp(const char* str1, const char* str2){
if(str1[0]=='\0'|| str2[0]=='\0') return str2[0] - str1[0];
int diff=0;
for(int n=0;str1[n]!='\0' && str2[n]!='\0';n++){
diff = str2[n] - str1[n];
if(diff!=0) return diff;
}
return diff;
}
int getLCP(const char* str1, const char* str2){
int n;
for(n=0;str1[n]!='\0' && str2[n]!='\0';n++){
if(str2[n] - str1[n]) break;
}
return n;
}
//adjacent list
int N;
char str[MAX_N + 1];
int suffixArray[MAX_N + 1];
int LCP[MAX_N + 1];
void quick_sort(int first, int last){
int pivot, j, temp, i;
if(first < last){
pivot = first;
i = first;
j = last;
while ( i < j){
while (my_strcmp((char*)(str + suffixArray[i]),(char*)(str + suffixArray[pivot])) >= 0 && i<last) i++;
while (my_strcmp((char*)(str + suffixArray[j]),(char*)(str + suffixArray[pivot])) < 0) j--;
if(i<j){
temp = suffixArray[i];
suffixArray[i] = suffixArray[j];
suffixArray[j] = temp;
}
}
temp = suffixArray[pivot];
suffixArray[pivot] = suffixArray[j];
suffixArray[j] = temp;
quick_sort(first,j-1);
quick_sort(j+1,last);
}
}
void calculateLCP(){
LCP[0] = 0;
for(int i=1;i<=N;i++){
LCP[i] = getLCP((char*)(str+suffixArray[i - 1]), (char*)(str+suffixArray[i]));
}
}
int main(){
int T, test_case;
freopen ( "sample_input.txt", "r", stdin );
cin >> T;
for(test_case = 1; test_case <= T; test_case++){
//initialization
//input
 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0; cin >> str;
cout << "["<<str<<"]" << endl;
N = my_strlen(str);
str[N] = '$';
str[N+1] = '\0';
//print suffix
cout << "1. Suffix list" << endl;
for(int i=0;i<=N;i++){
suffixArray[i] = i;
cout << "\t" << (i + 1) << " " << (char*)(str+suffixArray[i]) << endl;
}
quick_sort(0,N);
cout << "2. Suffix array" << endl;
for(int i=0;i<=N;i++){
cout << "\t" << (i + 1) << " " << (char*)(str+suffixArray[i]) << endl;
}
calculateLCP();
cout << "3. Suffix array and LCP" << endl;
for(int i=0;i<=N;i++){
cout << "\t" << (i + 1) << " "<< LCP[i] <<" " << (char*)(str+suffixArray[i]) << endl;
}
}
return 0;
}