-Flyぁ梦-

// r : 为字符串转化成的int数组, 0 - len-1 为源字符串, r[len] = 0
// sa : 1 - len有效, 值从0到len-1表示后缀序号
// rank : 0 - len-1有效, 值从1到len表示后缀字典序大小
// height : 2 - len有效, height[i] 为 sa[i]和sa[i-1]的LCP值
 
// da : n为字符串长度+1, m为字符集大小（用于基数排序）
// calh : n为字符串长度
 
#define MAX 40010
int height[MAX],rank[MAX],r[MAX],sa[MAX];
int ts[MAX],ta[MAX],tb[MAX],tv[MAX],pos;
bool cmp(int *y,int a,int b,int l){
    return y[a]==y[b]&&y[a+l]==y[b+l];
}
//计算sa和rank数组
void da(int n,int m){
    int i,j,*x=ta,*y=tb,p;
    for(i=0;i<m;i++) ts[i]=0;
    for(i=0;i<n;i++) ts[x[i]=r[i]]++;
    for(i=1;i<m;i++) ts[i]+=ts[i-1];
    for(i=n-1;i>=0;i--) sa[--ts[x[i]]]=i;
    for(j=1,p=1;p<n;j*=2,m=p){
        p=0;
        for(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++) ts[i]=0;
        for(i=0;i<n;i++) tv[i]=x[y[i]];
        for(i=0;i<n;i++) ts[tv[i]]++;
        for(i=1;i<m;i++) ts[i]+=ts[i-1];
        for(i=n-1;i>=0;i--) sa[--ts[tv[i]]]=y[i];
        swap(x,y);
        x[sa[0]]=0;
        p=1;
        for(i=1;i<n;i++){
            if(cmp(y,sa[i-1],sa[i],j)) x[sa[i]]=p-1;
            else x[sa[i]]=p++;
        }
    }
}
//计算height数组
void calh(int n){
    int i,k,tmp;
    for(i=1;i<=n;i++) rank[sa[i]]=i;
    k=0;
    for(i=0;i<n;i++){
        tmp=sa[rank[i]-1];
        for(;r[i+k]==r[tmp+k];k++) ;
        height[rank[i]]=k;
        k?--k:0;
    }
}
 
 
int main(){
	int N, len;
	char line[MAX];
	while(scanf("%d", &N) != EOF && N > 0){
		getchar();
		gets(line);
		len = strlen(line);
		for(int i = 0;i < len;i++) r[i] = line[i] - 'a' + 1;	// 须保证r数组的值都 > 0
		r[len] = 0;
		da(len + 1, 27); // 27表示所有r数组内的值必须小于这个值, r从1到26 (基数排序)
		calh(len);
	}
}