小 P 在看过电影《超时空接触》(Contact)之后被深深的打动，决心致力于寻
找外星人的事业。于是，他每天晚上都爬在屋顶上试图用自己的收音机收听外星
人发来的信息。虽然他收听到的仅仅是一些噪声，但是他还是按照这些噪声的高
低电平将接收到的信号改写为由 0 和 1 构成的串， 并坚信外星人的信息就隐藏在
其中。他认为，外星人发来的信息一定会在他接受到的 01 串中重复出现，所以
他希望找到他接受到的 01 串中所有重复出现次数大于 1 的子串。但是他收到的
信号串实在是太长了，于是，他希望你能编一个程序来帮助他。

输入文件的第一行是一个整数N ，代表小 P 接收到的信号串的长度。
输入文件第二行包含一个长度为N 的 01 串，代表小 P 接收到的信号串。

输出文件的每一行包含一个出现次数大于1 的子串所出现的次数。输出的顺
序按对应的子串的字典序排列。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

#define MAXN 3010*2

char str[MAXN];

int sa[MAXN],tsa[MAXN];

int rank[MAXN],trank[MAXN];

int buc[MAXN];

int height[MAXN];

int theight[MAXN];

void IndexSort(int jp,int n)

{

        memset(buc,,sizeof(buc));

        for (int i=;i<n;i++)buc[rank[i+jp]]++;

        for (int i=;i<=n;i++)buc[i]+=buc[i-];

        for (int i=n-;i>=;i--)tsa[--buc[rank[i+jp]]]=i;

        memset(buc,,sizeof(buc));

        for (int i=;i<n;i++)buc[rank[tsa[i]]]++;

        for (int i=;i<=n;i++)buc[i]+=buc[i-];

        for (int i=n-;i>=;i--)sa[--buc[rank[tsa[i]]]]=tsa[i];

}

void SuffixArray(char* str,int n)

{

        for (int i=;i<n;i++)trank[i]=str[i]-''+;

        for (int i=;i<n;i++)buc[trank[i]]++;

        for (int i=;i<=n;i++)buc[i]+=buc[i-];

        for (int i=n-;i>=;i--)sa[--buc[trank[i]]]=i;

        for (int i=,x=;i<n;i++)

        {

                if (!i || trank[sa[i]]!=trank[sa[i-]])x++;

                rank[sa[i]]=x;

        }

        for (int j=;j<n;j=j<<)

        {

                IndexSort(j,n);

                int x=;

                for (int i=;i<n;i++)

                {

                        if (!i || rank[sa[i]]!=rank[sa[i-]] || rank[sa[i]+j]!=rank[sa[i-]+j])x++;

                        trank[sa[i]]=x;

                }

                for (int i=;i<n;i++)rank[i]=trank[i];

                if (x==n)break;

        }

}

void InitHeight(int n)

{

        for (int i=;i<n;i++)

        {

                if (rank[i]==)continue;

                height[i]=max(height[i-]-,);

                while (i+height[i]<n && sa[rank[i]-]+height[i]<n

                                && str[i+height[i]]==str[sa[rank[i]-]+height[i]])

                        height[i]++;

        }

        for (int i=;i<n;i++)

                theight[i]=height[sa[i]];

}

vector<int> vec;

int stack[MAXN],tops=-;

int main()

{

        freopen("input.txt","r",stdin);

        int n;

        int x;

        scanf("%d\n",&n);

        scanf("%s\n",str);

        SuffixArray(str,n);

        InitHeight(n);

    //    for (int i=0;i<n;i++)printf("%d ",sa[i]);printf("\n");

    //    for (int i=0;i<n;i++)printf("%s\n",str+sa[i]);printf("\n");

    //    for (int i=0;i<n;i++)printf("%d ",height[i]);printf("\n");

        for (int i=;i<n;i++)

        {

                if (theight[i]<=theight[i-])continue;

                x=i;

                for (int k=theight[i];k>theight[i-];k--)

                {

                        while (x+<n && theight[x+]>=k)x++;

                        stack[++tops]=x-i+;

                }

                while (~tops)

                        printf("%d\n",stack[tops--]);

        }

}