# Cod sursa(job #2342429)

Utilizator Data 12 februarie 2019 20:03:54 Substr 80 cpp-64 done Arhiva de probleme 1.2 kb
``````#include<fstream>
#include<iostream>
#include<cstring>
#include<algorithm>
#define v1 first.first
#define v2 first.second
#define s second
#define mod 1000000007
using namespace std;
ifstream fin("substr.in");
ofstream fout("substr.out");
int b,p,n,k,sol,i,v[20][16400],nr,f[16400];
pair<pair<int,int>,int> d[16400];
char c[16400];
int lca(int i, int j)
{
int val=(1<<p),h=p,st=0;
while(val)
{
if(v[h][i]==v[h][j])
st+=val,i+=val,j+=val;
h--;val/=2;
}
return st;
}
int main()
{
fin>>n>>k;
if(k==1){fout<<n;return 0;}
fin>>c;
for(i=0;i<n;i++)
v[0][i]=c[i]-'0';
for(p=0,b=1;b<=n;p++,b<<=1)
{
for(i=0;i<n;i++)
{
d[i].v1=v[p][i];
if(i+b>=n) d[i].v2=-1;
else d[i].v2=v[p][i+b];
d[i].s=i;
}
sort(d+1, d+n+1);nr=-1;
for(i=0;i<n;i++)
{
if(i!=0&&d[i].v1==d[i-1].v1&&d[i].v2==d[i-1].v2) v[p+1][d[i].s]=v[p+1][d[i-1].s];
else v[p+1][d[i].s]=++nr;
}
}
for(i=0;i<n;i++) f[v[p][i]]=i;
for(i=0;i+k-1<n;i++) sol=max(sol, lca(f[i], f[i+k-1]));
fout<<sol;
return 0;
}
``````