Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #71 C問題 - Beaver (この記事を編集する[管理者用])

Source

Codeforces Beta Round #71 C問題 (1500pt)
Problem description
Beta Round #71の自分の参加記録

問題概要

10^5文字以下の文字列Xが与えられる.
また,10文字以下の文字列が10個以下与えられる.
Xの部分文字列で,与えられた文字列をどれも含まないもののうち,最長のものを求める問題.
複数あるならどれでも良い.

解法

greedyに尺取メソッドで求めれば良い.

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

int get_len(char a[]){
  int i;
  for(i=0;;i++) if(a[i]<' ') break;
  return i;
}

int is_same(char a[],char b[],int len){
  int i;
  rep(i,len) if(a[i]!=b[i]) return 0;
  return 1;
}

int n;
char in[111110]; int len;
char dic[12][122]; int dic_len[12];

int res1, res2;

int main(){
  int i,j,k,l,m;
  int st, ed;

  while(scanf("%s%d",in,&n)==2){
    res1 = res2 = 0;
    rep(i,n) scanf("%s",dic[i]);

    len = get_len(in);
    rep(i,n) dic_len[i] = get_len(dic[i]);

    st = 0;
    rep(ed,len){
      rep(i,n){
        if(ed-st+1 < dic_len[i]) continue;
        if(!is_same(dic[i],in+ed-dic_len[i]+1,dic_len[i])) continue;
        st = ed-dic_len[i]+2;
      }

      if(ed-st+1 > res1){
        res1 = ed-st+1;
        res2 = st;
      }
    }

    printf("%d %d\n",res1,res2);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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