思路

可以二分答案+哈希

判断有没有那个长为L的串出现至少m次即可

代码

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <map>

using namespace std;

int n,m;

const int base = 131;

unsigned long long hashx[80000],power[80000];

int ans=0,lastans=0;

char s[80000];

void init(){

    memset(hashx,0,sizeof(hashx));

    memset(power,0,sizeof(power));

    ans=0;

    lastans=0;

}

void get_hash(void){

    power[0]=1;

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

        hashx[i]=hashx[i-1]*base+s[i];

        power[i]=power[i-1]*base;

    }

}

unsigned long long hashs(int l,int r){

    return hashx[r]-hashx[l-1]*power[r-l+1];

}

struct MapNode{

    int times,pos;

    bool operator < (const MapNode &b) const{

        return b.times<times;

    }

};

map<unsigned long long,MapNode> M;

bool check(int x){

    M.clear();

    ans=0;

    for(int i=1;i+x-1<=n;i++){

        M[hashs(i,i+x-1)].times++;

        M[hashs(i,i+x-1)].pos=i;

    }

    bool f=false;

    for(auto it = M.begin();it!=M.end();it++){

        if((*it).second.times>=m){

            f=true;

            ans=max(ans,(*it).second.pos);

        }

    }

    return f;

}

int main(){

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

    // freopen("test.out","w",stdout);

    while(scanf("%d",&m)==1&&m){

        init();

        scanf("%s",s+1);

        n=strlen(s+1);

        get_hash();

        int l=0,r=n,t=0;

        while(l<=r){

            int mid=(l+r)>>1;

            if(check(mid))

                lastans=ans,t=mid,l=mid+1;

            else

                r=mid-1;

        }

        if(t){

            printf("%d %d\n",t,lastans-1);

        }

        else{

            printf("none\n");

        }

    }

    return 0;

}