DTKSUB - Chuỗi con xuất hiện K lần
Tác giả: skyvn97
Ngôn ngữ: C++
#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 MASK(i) (1<<(i))
#define tget(i) ((t[(i)/8]&MASK((i)%8))?1:0)
#define tset(i,b) t[(i)/8]=(b)?(t[(i)/8]|MASK((i)%8)):(t[(i)/8]&(~MASK((i)%8)))
#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;
}