Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #75 DIV1 A問題/DIV2 C問題 - Newspaper Headline (この記事を編集する[管理者用])

Source

Codeforces Beta Round #72 DIV1 A問題 (500pt)
Codeforces Beta Round #72 DIV2 C問題 (1500pt)
Problem description

問題概要

長さ10^4以下の文字列Aと長さ10^6以下の文字列Bが与えられる.
文字列はアルファベット小文字のみからなる.
Aをk回繰り返してできる文字列をA^kと書くことにして,A^kがBを部分列にもつような最小のkを求める問題.
そんなkが存在しないならそれを指摘する.

解法

Bにしか含まれない文字が存在するなら-1.
Aの各場所から,次に各文字が登場する場所を全部最初に記憶しておく.
後は,愚直に,A[0]が最初に現れる場所,その場所移行でA[1]が最初に現れる場所,…と辿っていく.

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)

char a[11000], b[1100000];
int as, bs;

int next[11000][26];

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

  while(scanf("%s%s",a,b)==2){
    for(as=0;;as++) if(a[as]<' ') break;
    for(bs=0;;bs++) if(b[bs]<' ') break;

    rep(i,as) a[i] -= 'a';
    rep(i,bs) b[i] -= 'a';

    res = 1;
    rep(i,as+1){
      rep(j,26) next[i][j] = -1;
      REP(k,i,as) if(next[i][a[k]]==-1) next[i][a[k]] = k;
    }

    now = 0;
    rep(i,bs){
      if(next[now][b[i]]==-1){
        if(now==0){ res=-1; break; }
        res++; now=0; i--; continue;
      }

      now = next[now][b[i]]+1;
    }

    printf("%d\n",res);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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