你是否经常在写完文章之后为文章取一个合适的标题而苦恼？这里提供一个很有趣的方法。
首先，标题应该概括文章的内容。为了简单起见，如果一个短语在文章中不重叠地出现了至少k次，那么这个短语就可以作为标题。例如，”dadadad”中，短语”dad” 不重叠地出现了两次，而不是三次。
其次，标题越长越好。长标题才能吸引眼球。
最后，这件事应该让计算机来做比较省事。
所以，请编写一个程序，根据给定的k和一段文章，给这篇文章取个标题。

输入包括多组数据。
每组数据第一行为整数k，第二行为一个字符串表示文章内容，为了简化问题，字符串仅含小写字母。字符串长度不超过10000。
输入数据以k=0结束。

对每组数据输出最长的标题长度，如果找不到符合要求的标题，则输出0。

#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long ulint;

#define maxn 23333

const ulint x=;

int M;

char in[maxn];

ulint has[maxn];

int pos[maxn];

int id[maxn];

ulint xp[maxn];

ulint H[maxn];

bool cmp(int a,int b)

{

    return has[a]<has[b]||has[a]==has[b]&&a<b;

}

bool check(int mid,int n)

{

    pos[mid]=;

    id[]=;

    for(int i=; i+mid-<n; i++)//就算每一段的hash值

        id[i]=i,has[i]=H[i]-H[i+mid]*xp[mid];

    sort(id,id+n-mid+,cmp);//按hash值排序

    int cnt=;

    bool ret=;

    int tmp=id[];

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

        if(has[id[i]]==has[id[i-]])

        {

            if(id[i]-tmp>=mid)

            cnt++,tmp=id[i];

            if(cnt>=M)

                pos[mid]=max(pos[mid],tmp),ret=;

        }

        else

            cnt=,tmp=id[i];

    return ret;

}

int main()

{

    xp[]=;

    for(int i=; i<maxn; i++)//预处理x次幂项

        xp[i]=xp[i-]*x;

    while(scanf("%d",&M),M)

    {

        scanf("%s",in);

        int n=strlen(in);

        if(M==)

        {

            printf("%d\n",n);

            continue;

        }

        H[n]=;

        for(int i=n-; i >= ; i--)//预处理H[i]=s[i]+s[i+1]*x+...+s[n]*x^(n-i)

            H[i]=H[i+]*x+(in[i]-'a');

        int L=,R=n,mid,len=;

        while(L<=R)

        {

            mid=(L+R)>>;

            if(check(mid,n))

            {

                len=mid;

                L=mid+;

            }

            else

                R=mid-;

        }

        if(len==)

            printf("0\n");

        else

            printf("%d\n",len);

    }

    return ;

}

#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <string.h>

#include <set>

#define dbg(x) std::cout<<#x<<" = "<< (x)<< "\n"

#define maxn 20005

int wa[maxn],wb[maxn],wv[maxn],ws[maxn],m;

int cmp(int *r,int a,int b,int l)

{

    return r[a]==r[b]&&r[a+l]==r[b+l];

}

void getsa(int *r,int *sa,int n,int m)

{

    int i,j,p,*x=wa,*y=wb,*t;

    for(i=; i<m; i++) ws[i]=;

    for(i=; i<n; i++) ws[x[i]=r[i]]++;

    for(i=; i<m; i++) ws[i]+=ws[i-];

    for(i=n-; i>=; i--) sa[--ws[x[i]]]=i;

    for(j=,p=; p<n; j*=,m=p)

    {

        for(p=,i=n-j; i<n; i++) y[p++]=i;

        for(i=; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;

        for(i=; i<n; i++) wv[i]=x[y[i]];

        for(i=; i<m; i++) ws[i]=;

        for(i=; i<n; i++) ws[wv[i]]++;

        for(i=; i<m; i++) ws[i]+=ws[i-];

        for(i=n-; i>=; i--) sa[--ws[wv[i]]]=y[i];

        for(t=x,x=y,y=t,p=,x[sa[]]=,i=; i<n; i++)

            x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;

    }

}

int rank[maxn],height[maxn];

void calheight(int *r,int *sa,int n)

{

    int i,j,k=;

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

    for(i=; i<n; height[rank[i++]]=k)

        for(k?k--:,j=sa[rank[i]-]; r[i+k]==r[j+k]; k++);

}

int a[maxn];

int check(int *sa,int n,int k)

{

    int i,cnt=;

    a[]=sa[];

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

    {

        if(height[i]>=k)

        {

            a[cnt++]=sa[i];

        }

        else

        {

            if(cnt>=m)

            {

                std::sort(a,a+cnt);

                int x=a[],tot=cnt;

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

                {

                    if(a[i]-x<k)cnt--;

                    else x=a[i];

                }

                if(cnt>=m)return ;

            }

            cnt=,a[]=sa[i];

        }

    }

    std::sort(a,a+cnt);

    int x=a[],tot=cnt;

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

    {

        if(a[i]-x<k)cnt--;

        else x=a[i];

    }

    if(cnt>=m)return ;

    return ;

}

int r[maxn],sa[maxn];

char str[maxn];

int main()

{

    //freopen("test.in","r",stdin);

    while(scanf("%d",&m),m)

    {

        scanf("%s",str);

        int n=strlen(str);

        if(m==)

        {

            printf("%d\n",n);

            continue;

        }

        for(int i=; i<n; i++)r[i]=str[i];

        r[n]=;

        getsa(r,sa,n+,);

        calheight(r,sa,n);

        int L=,R=n,mi,len=;

        while(L<=R)

        {

            mi=(L+R)>>;

            if(check(sa,n,mi))L=mi+,len=mi;

            else R=mi-;

        }

        printf("%d\n",len);

    }

    return ;

}