Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2169-e470305a
この記事にトラックバックする(FC2ブログユーザー)

Beta Round #94 DIV1 B問題/DIV2 D問題 - String (この記事を編集する[管理者用])

Source

Codeforces Beta Round #93 DIV1 B問題 (1500pt)
Codeforces Beta Round #93 DIV2 D問題 (2500pt)
Problem description

問題概要

長さ10^5以下のアルファベット小文字のみからなる文字列が与えられる.
その空でない部分文字列 (重複も含めて) を全部もってきて,ソートした時,k番目のものを答える問題.
kは10^5以下.

解法

Suffix ArrayとLCPを使って,1番目から列挙してあげた.O(length log length + k)ぐらい.
他の方法は,最初,全部一文字の部分文字列をheapにつっこみ,小さい順に取り出す.
取り出されたものに,後ろを一文字加えて突っ込み直す.というのをk回繰り返せば良い.
その際,文字列の比較が重たいので,ローリングハッシュで,どの部分文字列が一緒かを判定できるようにしておいて,最初に異なる文字を二分探索で探すなどすればO(length (log length)^2)とかになると思う.
後,実は,一文字ずつ確定して行っても,O(length^1.5)とかになって通るのかもしれない.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long
void llIntSort(ll d[],int m[],int s){int i,j,a;ll k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;i=-1;j=s;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;a=m[i];m[i]=m[j];m[j]=a;}llIntSort(d,m,i);llIntSort(d+j+1,m+j+1,s-j-1);}

void charCreateSuffixArray(char t[], int n, int res[], void *WorkMemory) {
  int i, h, *g, *b; ll *d;

  g = (int*)WorkMemory; WorkMemory = (void*)(g+n+1);
  b = (int*)WorkMemory; WorkMemory = (void*)(b+n+1);
  d = (ll*) WorkMemory;
  
  rep(i,n+1) res[i] = i, d[i] = g[i] = t[i];
  b[0] = 0; b[n] = 0;

  llIntSort(d,res,n+1);
  for(h=1;b[n]!=n;h*=2){
    rep(i,n+1){
      d[i] = g[res[i]] * (1LL<<32);
      if(res[i]+h<n+1) d[i] += g[res[i]+h];
    }
    llIntSort(d,res,n+1);
    rep(i,n){ b[i+1]=b[i]; if(g[res[i]]!=g[res[i+1]]||g[res[i]+h]!=g[res[i+1]+h]) b[i+1]++; }
    rep(i,n+1) g[res[i]]=b[i];
  }
}

void charCreateLCPFromSA(char *t, int n, int *SA, int *res, void *WorkMemory) {
  int i, j, h=0, *b;

  b = (int*)WorkMemory;

  rep(i,n+1) b[SA[i]]=i;
  rep(i,n+1){
    if(b[i]){
      for(j=SA[b[i]-1];j+h<n&&i+h<n&&t[j+h]==t[i+h];h++);
      res[b[i]]=h;
    }else res[b[i]] = -1;
    if(h>0)h--;
  }
}

char in[200000];
int SA[200000], LCP[200000], len[200000];

int main(){
  int i,j,k,l,m,n,ok;
  void *mem = malloc(10000000);

  while(scanf("%s%d",in,&m)==2){
    n = strlen(in);
    charCreateSuffixArray(in, n, SA, mem);
    charCreateLCPFromSA(in, n, SA, LCP, mem);

    rep(i,n+1) len[i] = n-SA[i];
/*    rep(i,n+1) printf("%d %d %d %d\n",i,SA[i],LCP[i],len[i]);*/
    
    m--; ok = 0;
    REP(i,1,n+1){
      REP(j,LCP[i]+1,len[i]+1){
        REP(k,i,n+1){
          if(k>i && LCP[k]<j) break;
          if(!m){
            rep(l,j) putchar(in[SA[i]+l]);
            ok = 1; break;
          } else {
            m--;
          }
        }
        if(ok) break;
      }
      if(ok) break;
    }

    if(!ok) printf("No such line.");
    puts("");
  }
  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2169-e470305a
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。