2019年08月21日05時21分55秒に更新されたバージョンを表示しています．
最新のページはこちらをご覧ください．

Codeforces Round #579 DIV3 D2問題 - Remove the Substring (hard version)

Source

Codeforces Round #579 DIV3 D2問題
Problem description

問題概要

省略

解法

省略

cLay（version 20190820-1）のコード

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

//no-unlocked
char S[200002], T[200002];
int Slen, Tlen;

int dp1[200001], dp2[200001];

{
  int i, j, res = 0;
  rd(S@Slen, T@Tlen);

  j = 0;
  rep(i,Slen){
    if(j < Tlen && S[i] == T[j]) j++;
    dp1[i] = j;
  }

  j = 0;
  for(i=Slen-1;i>=0;i--){
    if(j < Tlen && S[i] == T[Tlen-1-j]) j++;
    dp2[i] = j;
  }

  j = 0;
  while(j+1 <= Slen && dp2[j+1] >= Tlen) j++;
  res >?= j;
  
  rep(i,Slen){
    while(j+1 <= Slen && dp1[i] + dp2[j+1] >= Tlen) j++;
    res >?= j - i - 1;
  }

  wt(res);
}

Current time: 2024年04月23日15時25分44秒
Last modified: 2019年08月21日05時21分55秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF579 CF_Div3_D
トップページに戻る

Logged in as: unknown user (not login)