Cod sursa(job #2468034)

Utilizator Stefan_PiscuPiscu Stefan Constantin Stefan_Piscu Data 5 octombrie 2019 11:54:34
Problema Substr Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 2000

ifstream fin("substr.in");
ofstream fout("substr.out");

struct suffix
{
    int index;
    pair<int, int> x;
};

int sfar[NMAX];

bool cmp(suffix x, suffix y)
{
    return x.x<y.x||(x.x==y.x&&x.index<y.index);
}

int n;

string s;

void build()
{
    int ind[NMAX];
    suffix tsfar[NMAX];
    for(int i=0;i<n;++i)
    {
        tsfar[i].index=i;
        tsfar[i].x.first=s[i]-'a';
        if(i+1<n) tsfar[i].x.second=s[i+1]-'a';
        else tsfar[i].x.second=-10000;
    }
    sort(tsfar, tsfar+n, cmp);
    for(int k=4;k<2*n;k*=2)
    {
        int r=0;
        pair<int, int> x=tsfar[0].x;
        tsfar[0].x.first=r;
        ind[tsfar[0].index]=0;
        for(int i=1;i<n;++i)
        {
            if(tsfar[i].x==x) tsfar[i].x.first=r;
            else
            {
                r++;
                x=tsfar[i].x;
                tsfar[i].x.first=r;
            }
            ind[tsfar[i].index]=i;
        }
        for(int i=0;i<n;++i)
        {
            if(tsfar[i].index+k/2<n) tsfar[i].x.second=tsfar[ind[tsfar[i].index+k/2]].x.first;
            else tsfar[i].x.second=-10000;
        }
        sort(tsfar, tsfar+n, cmp);
    }
    for(int i=0;i<n;++i) sfar[i]=tsfar[i].index;
}

int lcp[NMAX];

int rmq[NMAX][10];

void buildrmq()
{
    for(int i=0;i<n;++i) rmq[i][0]=lcp[i];
    for(int j=1;(1<<j)<=NMAX;++j)
    {
        for(int i=0;i+(1<<(j-1))<n;++i)
        {
            rmq[i][j]=min(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
        }
    }
}

int ind[NMAX];

int query(int i, int j)
{
    j--;
    int k=0;
    while((1<<k)<=j-i+1) k++;
    k--;
    return min(rmq[i][k], rmq[j-(1<<k)+1][k]);
}



void kasai()
{
    for(int i=0;i<n;++i)
    {
        ind[sfar[i]]=i;
    }
    int k=0;
    for(int i=0;i<n;++i)
    {
        if(ind[i]==n-1)
        {
            k=0;
        }
        else
        {
            int j=sfar[ind[i]+1];
            while(i+k<n&&j+k<n&&s[i+k]==s[j+k]) k++;
        }
        lcp[ind[i]]=k;
        if(k>0) k--;
    }
}

int k;

int main()
{
    fin>>n>>k>>s;
    build();
    kasai();
    buildrmq();
    int sol=0;
    for(int i=0;i<n;++i)
    {
        int x=query(i, i+k-1);
        if(x>sol) sol=x;
    }
    fout<<sol<<"\n";
    return 0;
}