保存されている過去のバージョンの一覧

AtCoder Beginner Contest 138 E問題 - Strings of Impurity

Source

AtCoder Beginner Contest 138
問題文

問題概要

省略

解法

省略

cLay（version 20190820-1）のコード

C++に変換後のコードはこちら

char S[200002], T[100002];
int Slen, Tlen;

int nx[26][200002];

{
  int i, j, k, c;
  ll res;

  rd(S@Slen, T@Tlen);

  rep(i,Slen) S[i] -= 'a';
  rep(i,Tlen) T[i] -= 'a';
  rep(i,Slen) S[i+Slen] = S[i];

  rep(k,26){
    nx[k][2Slen-1] = int_inf;
    for(i=2Slen-2;i>=0;i--){
      nx[k][i] = nx[k][i+1];
      if(S[i+1]==k) nx[k][i] = i+1;
    }
  }

  k = Slen-1;
  res = -1;
  rep(i,Tlen){
    c = T[i];
    if(nx[c][k]==int_inf){ wt(-1); return 0; }
    k = nx[c][k];
    if(k >= Slen) k -= Slen, res++;
  }
  res = res * Slen + k + 1;
  wt(res);
}

Current time: 2024年04月27日14時17分06秒
Last modified: 2019年08月22日01時05分19秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC138 ABC_E
トップページに戻る

Logged in as: unknown user (not login)