Hướng dẫn giải của Chuỗi con xuất hiện K lần
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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; }
Bình luận