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.
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
Code mẫu của ladpro98
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); readln(inp,n,k);readln(inp,s); 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 readln(f1,n,k); for i:=1 to n do begin read(f1,c); 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 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; }
Comments