Editorial for Chuỗi con xuất hiện K lần

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

program DTKSUB;
uses    math;
const   base = 26;
hash = trunc(1e9)+13;
hash2 = hash*hash;
maxn=50004;
fi='';
var
h,pow,ph:array[0..maxn] of int64;
f:array[0..maxn] of longint;
inp:text;
res,n,k,i,l,r,m,oa:longint;
ok:boolean;
s:ansistring;

procedure sort(l,r:longint);
var     p,t,i,j:longint;
begin
if l>=r then exit;
i:=l;j:=r;
p:=h[random(r-l+1)+l];
repeat
while h[i]<p do inc(i);
while h[j]>p do dec(j);
if i<=j then begin
if i<j then begin
t:=h[i];
h[i]:=h[j];
h[j]:=t;
end;
inc(i);dec(j);
end;
until i>j;
sort(l,j);sort(i,r);
end;

begin
assign(inp,fi);reset(inp);
if k=1 then begin
write(n);
halt;
end;
pow[0]:=1;oa:=ord('a');
for i:=1 to n do pow[i]:=(base*pow[i-1]) mod hash;
for i:=1 to n do ph[i]:=(base*ph[i-1]+ord(s[i])-oa) mod hash;

l:=1;r:=n;
while l<=r do begin
m:=(l+r) shr 1;
for i:=m to n do h[i]:=(ph[i] - pow[m]*ph[i-m] + hash2) mod hash;
sort(m,n);
f[m]:=1;ok:=false;
for i:=m+1 to n do begin
if h[i] = h[i-1] then f[i]:=f[i-1]+1
else f[i]:=1;
if f[i]>=k then begin
ok:=true;
break;
end;
end;
if (ok) then begin
l:=m+1;
res:=m;
end
else    r:=m-1;
end;
write(res);
end.


Code mẫu của RR

//Written by RR

{\$MODE OBJFPC}

uses math;
const
FINP          =       '';
FOUT          =       '';
MAXN          =       50111;
hashkey       =       1000003;

var
f1,f2         :       text;
n,k           :       longint;
count         :       array[0..hashkey] of longint;
sum,lt,a      :       array[0..MAXN] of longint;

procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;

procedure closeF;
begin
close(f1);
close(f2);
end;

procedure inp;
var
i:longint;
c:char;
begin
for i:=1 to n do
begin
a[i]:=ord(c)-ord('a');
end;
end;

function check(val:longint):boolean;
var
i,j,tmp:longint;
begin
fillchar(count,sizeof(count),0);
for i:=1 to n-val+1 do
begin
j:=i+val-1;

tmp:=(int64(lt[n-i])*(sum[j]-sum[i-1]+hashkey)) mod hashkey;
inc(count[tmp]);
if count[tmp]>=k then exit(true);
end;
exit(false);
end;

procedure solve;
var
i,l,r,mid,res:longint;
begin
lt[0]:=1;
for i:=1 to n do
lt[i]:=(lt[i-1]*26) mod hashkey;
for i:=1 to n do
sum[i]:=(sum[i-1]+a[i]*lt[i-1]) mod hashkey;

l:=1; r:=n; res:=0;
while l<=r do
begin
mid:=(l+r) shr 1;
if check(mid) then
begin
res:=mid;
l:=mid+1;
end
else r:=mid-1;
end;
writeln(f2,res);
end;

begin
openF;
inp;
solve;
closeF;
end.


Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>
#include <cassert>

using namespace std;

typedef long long ll;
typedef double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int i = (a); i >= (b); --i)
#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }

typedef pair<int, int> II;

const double PI = acos(-1.0);
const double eps = 1e-9;

const int dr[] = {-1, 0, +1, 0};
const int dc[] = {0, +1, 0, -1};

const int inf = (int)1e9 + 5;
const ll linf = (ll)1e17 + 5;
const ll mod = (ll)1e9 + 7;

#define maxn 200005
#define maxa 30

int n, m, from, to, nc, a[maxn], p[maxn], c[maxn], pn[maxn], cn[maxn], cnt[maxn], lcp[maxn];
char s[maxn];

void suffix_array() {
Rep(i, n) a[i] = s[i] - 'a' + 1;
a[n++] = 0;

ms(cnt, 0);
Rep(i, n) ++cnt[a[i]];
For(i, 1, maxa - 1) cnt[i] += cnt[i - 1];
Repd(i, n) p[--cnt[a[i]]] = i;

nc = 1; c[p[0]] = 0;
For(i, 1, n - 1) {
if (a[p[i]] > a[p[i - 1]]) ++nc;
c[p[i]] = nc - 1;
}

for (int h = 1; h < n; h <<= 1) {
Rep(i, n) {
pn[i] = p[i] - h;
if (pn[i] < 0) pn[i] += n;
}

ms(cnt, 0);
Rep(i, n) ++cnt[c[pn[i]]];
For(i, 1, nc - 1) cnt[i] += cnt[i - 1];
Repd(i, n) p[--cnt[c[pn[i]]]] = pn[i];

nc = 1; cn[p[0]] = 0;
For(i, 1, n - 1) {
int x = (p[i] + h) % n, y = (p[i - 1] + h) % n;
if (c[p[i]] > c[p[i - 1]] || c[x] > c[y]) ++nc;
cn[p[i]] = nc - 1;
}
Rep(i, n) c[i] = cn[i];
}

int h = 0;
Rep(i, n) {
if (c[i] > 0) {
int j = p[c[i] - 1];
while (a[i + h] == a[j + h]) ++h;
lcp[c[i]] = h;
if (h > 0) --h;
}
}

}

bool check(int d){
if(d > n) return false;
int run = 1, MAX = 0;
For(i, 1, n - 1){
if(lcp[i] < d){
run = 1;
}
else run++;
MAX = max(run, MAX);
}
return MAX >= m;
}

int main(){
//    freopen("in.txt", "r", stdin);
cin >> n >> m;
scanf("%s", s);
suffix_array();
int l = 1, r = n, mid;
while(l < r){
mid = (l + r) >> 1;
if(check(mid)){
l = mid + 1;
}
else r = mid;
}

cout << l - 1 << endl;

return 0;
}


Code mẫu của skyvn97

#include<deque>
#include<iostream>
#include<string>
#include<vector>
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define FORD(i,b,a) for (int i=(b);i>=(a);i=i-1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define chr(i) ((cs==sizeof(int))?((int *)s)[i]:((unc *)s)[i])
#define isLMS(i) ((i)>0 && tget(i) && !tget((i)-1))
using namespace std;
typedef unsigned char unc;
class SuffixArray {
private:
int *sa,*lcp,*rank,n;
unc *s;
void getbuckets(unc s[],vector<int> &bkt,int n,int k,int cs,bool end) {
FOR(i,0,k) bkt[i]=0;
REP(i,n) bkt[chr(i)]++;
int sum=0;
FOR(i,0,k) {
sum+=bkt[i];
bkt[i]=end?sum:sum-bkt[i];
}
}
void inducesal(vector<unc> &t,int sa[],unc s[],vector<int> &bkt,int n,int k,int cs,bool end) {
getbuckets(s,bkt,n,k,cs,end);
REP(i,n) {
int j=sa[i]-1;
if (j>=0 && !tget(j)) sa[bkt[chr(j)]++]=j;
}
}
void inducesas(vector<unc> &t,int sa[],unc s[],vector<int> &bkt,int n,int k,int cs,bool end) {
getbuckets(s,bkt,n,k,cs,end);
FORD(i,n-1,0) {
int j=sa[i]-1;
if (j>=0 && tget(j)) sa[--bkt[chr(j)]]=j;
}
}
void build(unc s[],int sa[],int n,int k,int cs) {
int j;
vector<unc> t=vector<unc>(n/8+1,0);
tset(n-2,0);
tset(n-1,1);
FORD(i,n-3,0) tset(i,(chr(i)<chr(i+1) || (chr(i)==chr(i+1) && tget(i+1)))?1:0);
vector<int> bkt=vector<int>(k+1,0);
getbuckets(s,bkt,n,k,cs,true);
REP(i,n) sa[i]=-1;
REP(i,n) if (isLMS(i)) sa[--bkt[chr(i)]]=i;
inducesal(t,sa,s,bkt,n,k,cs,false);
inducesas(t,sa,s,bkt,n,k,cs,true);
bkt.clear();
int n1=0;
REP(i,n) if (isLMS(sa[i])) sa[n1++]=sa[i];
FOR(i,n1,n-1) sa[i]=-1;
int name=0;
int prev=-1;
REP(i,n1) {
int pos=sa[i];
bool diff=false;
REP(d,n) {
if (prev<0 || chr(prev+d)!=chr(pos+d) || tget(prev+d)!=tget(pos+d)) {
diff=true;
break;
}
else if (d>0 && (isLMS(prev+d) || isLMS(pos+d))) break;
}
if (diff) {
name++;
prev=pos;
}
sa[n1+pos/2]=name-1;
}
j=n-1;
FORD(i,n-1,n1) if (sa[i]>=0) sa[j--]=sa[i];
int *sa1=sa;
int *s1=sa+n-n1;
if (name<n1) build((unc *)s1,sa1,n1,name-1,sizeof(int));
else REP(i,n1) sa1[s1[i]]=i;
bkt.assign(k+1,0);
getbuckets(s,bkt,n,k,cs,true);
j=0;
REP(i,n) if (isLMS(i)) s1[j++]=i;
REP(i,n1) sa1[i]=s1[sa1[i]];
FOR(i,n1,n-1) sa[i]=-1;
FORD(i,n1-1,0) {
j=sa[i];
sa[i]=-1;
sa[--bkt[chr(j)]]=j;
}
inducesal(t,sa,s,bkt,n,k,cs,false);
inducesas(t,sa,s,bkt,n,k,cs,true);
bkt.clear();
t.clear();
}
void calc_lcp(void) {
FOR(i,1,n) rank[sa[i]]=i;
int h=0;
REP(i,n) if (rank[i]<n) {
int j=sa[rank[i]+1];
while (s[i+h]==s[j+h]) h++;
lcp[rank[i]]=h;
if (h>0) h--;
}
}
void count(int k) {
if (k==0) {
cout << n;
return;
}
int res=0;
deque<int> dq;
while (!dq.empty()) dq.pop_back();
FOR(i,1,n-1) {
while (!dq.empty() && lcp[i]<=lcp[dq.back()]) dq.pop_back();
dq.push_back(i);
if (i>=k) {
while (!dq.empty() && dq.front()<=i-k) dq.pop_front();
res=max(res,lcp[dq.front()]);
}
}
cout << res;
}
public:
SuffixArray() {
n=0;
sa=NULL;lcp=NULL;rank=NULL;
s=NULL;
}
SuffixArray(string &ss,int k) {
n=ss.size();
sa=new int[n+7];
lcp=new int[n+7];
rank=new int[n+7];
s=(unc *)ss.c_str();
build(s,sa,n+1,256,sizeof(char));
calc_lcp();
//FOR(i,1,n) printf("%d %d\n",sa[i],lcp[i]);
count(k-1);
}
};
int main(void) {
ios::sync_with_stdio(false);
int n,k;
string s;
cin >> n >> k >> s;
SuffixArray SA=SuffixArray(s,k);
return 0;
}