Cod sursa(job #756768)

Utilizator ChallengeMurtaza Alexandru Challenge Data 10 iunie 2012 13:49:26
Problema Substr Scor 100
Compilator cpp Status done
Runda Remember Mihai Pătrașcu Marime 1.3 kb
#include <fstream>
#include <algorithm>

using namespace std;

const char InFile[]="substr.in";
const char OutFile[]="substr.out";
const int MaxN=16500;
const int LogMaxN=17;

ifstream fin(InFile);
ofstream fout(OutFile);

struct Suffix
{
	int pos,ms,ls;
};

struct Suffix_cmp
{
	inline bool operator() (const Suffix &a, const Suffix &b)
	{
		if(a.ms!=b.ms)
		{
			return a.ms<b.ms;
		}
		return a.ls<b.ls;
	}
};

short int N,K,sol,P[LogMaxN][MaxN],logN;
char S[MaxN];
Suffix L[MaxN];

inline void SuffixArray()
{
	for(register int i=0;i<N;++i)
	{
		P[0][i]=(short int)(S[i]);
	}
	
	int stp,cnt;
	for(stp=1,cnt=1;cnt<N;++stp,cnt<<=1)
	{
		for(register int i=0;i<N;++i)
		{
			L[i].ms=P[stp-1][i];
			L[i].ls=i+cnt<N?P[stp-1][i+cnt]:-1;
			L[i].pos=i;
		}
		sort(L,L+N,Suffix_cmp());
		for(register int i=0;i<N;++i)
		{
			P[stp][L[i].pos]= i>0 && L[i].ms==L[i-1].ms && L[i].ls==L[i-1].ls?P[stp][L[i-1].pos]:i;
		}
	}
	logN=stp-2;
}

inline short int LCP(int x, int y)
{
	if(x==y)
	{
		return N-x;
	}
	int sol=0,stp=logN;
	for(;stp>=0;--stp)
	{
		if(P[stp][x]==P[stp][y])
		{
			int v=1<<stp;
			x+=v;
			y+=v;
			sol+=v;
		}
	}
	return sol;
}

int main()
{
	fin>>N>>K>>S;
	fin.close();
	
	SuffixArray();
	
	--K;
	for(register int i=0;i+K<N;++i)
	{
		sol=max(sol,LCP(L[i].pos,L[i+K].pos));
	}
	
	fout<<sol;
	fout.close();
	return 0;
}