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.

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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.