Cod sursa(job #30296)

Utilizator mariusdrgdragus marius mariusdrg Data 13 martie 2007 18:43:28
Problema Substr Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<stdio.h>
#include<algorithm>

const int maxn = 100001;
const int maxn2 = 17001;

int i ,j, n, k;
int nr[maxn];
char s[maxn2];
int x, p;
int h;
const int baza = 33;
int p1;



int ver(int len)
{
    p1 = 1;
    memset(nr,0,sizeof(nr));
    h = 0;
    for(i = 0;i < len; ++i)
    {
        if (i != 0)p1 *= baza;
        h *= baza;
        h += s[i] - 'a';
        h %= maxn;
        p1 %= maxn;
    }
    nr[h]++;
    for(j = len ;j <= n; ++j)
    {
        h -= (p1 * (s[j - len] - 'a')) % maxn;
        h += maxn;
        h *= baza;
        h += s[j] - 'a';
        h %= maxn;
        nr[h]++;
        if (nr[h] > k) return 1;
    }
    return 0;
}


int main()
{
    freopen("substr.in","r",stdin);
    freopen("substr.out","w",stdout);
    scanf(" %d %d ",&n,&k);
    scanf("%s",s);
    for(p = 1;p <= n; p <<= 1);
    for(;p ; p >>= 1)
    {
        if (ver(x + p))
        {
            x += p;
        }
    }

    printf("%d",x);
    return 0;
}