Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

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

問題概要

長さ10^6以下の文字列Sが与えられる.
Sのプレフィックスであり,Sのサフィックスでもあり,Sから最初と最後の文字を取り除いた文字列の部分文字列でもあるような文字列のうち最長のものを求める問題.
存在しないならそれを指摘する.

解法

候補は最初からk文字とってきた文字列だけなので,候補の数はたかだか10^6ぐらい.
最初からと,最後からと,ハッシュを計算しておく,などをして,先頭k文字と最後k文字が等しいかどうかの判定はO(1)でできるようにしておく.
kをn-1から1ずつ減らして行って,先頭からk文字が条件を満たすか調べていく.
最後k文字と一致していれば,間にそれを含むかどうかは,ローリングハッシュかKMPなどでO(len)かけて良い.
最初と最後が一致するのがたくさんあると,一見O(length^2)になりそうだけど,2つ目は必ず答えになって撃ち切れるのでO(length).
(2011-11-14 17:12追記) 2個目が答えになってる説明 http://twitpic.com/7e3lx1

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
#define ull unsigned ll

#define D 10007

char in[1100000];
ull hs, st[1100000], ed[1100000];
ull pw[1100000];

int main(){
  int i,j,k,l,m,n,ok,res;

  while(scanf("%s",in)==1){
    n = strlen(in);
    res = 0;

    pw[0] = 1;
    rep(i,n+1) pw[i+1] = pw[i]*D;

    st[0] = ed[0] = 0;
    rep(i,n) st[i+1] = st[i]*D + in[i];
    rep(i,n) ed[i+1] = ed[i] + in[n-1-i]*pw[i];

    for(k=n-1;k;k--) if(st[k]==ed[k]){
      ok = 0;
      hs = 0;
      rep(i,k) hs = hs*D + in[i];
      REP(i,k,n-1){
        hs = hs*D + in[i] - in[i-k]*pw[k];
        if(hs==st[k]) ok=1;
      }
      if(ok){res=k; break;}
    }
    
    if(res > 0){
      rep(i,res) putchar(in[i]);
      puts("");
    } else {
      puts("Just a legend");
    }
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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