0w1

CFR Educational 17 C. Two strings ( Ad hoc )

Problem - C - Codeforces

題意:
給字串 A, B,求最短的一個 B 的子字串,使得從 B 刪去這段子字串後的新字串 B' 為 A 的一個子序列。輸出 B'。

資料規模:
字串長度不超過 1e5
TL: 2000 ms
ML: 256 MB

解法:
由左到右枚舉 A 的字串的切割點,並透過預處理這個切割點左邊的字串可以滿足的最長 B 的前綴,和切割點右邊的字串可以滿足的最長 B 的後綴,便能 O( 1 ) 更新長度最短的刪除子字串。

時間 / 空間複雜度:
O( A + B )

string A, B;

void init(){
  cin >> A >> B;
}

const int MAXLEN = ( int ) 1e5;

int fptr[ MAXLEN + 1 ], bptr[ MAXLEN + 1 ]; // with split point at i, pending match is ptr[ i ]
int minkill;
string ans = "-";

void preprocess(){
  minkill = B.size();
  for( int i = 0; i < A.size(); ++i ){
    fptr[ i + 1 ] = fptr[ i ];
    if( A[ i ] == B[ fptr[ i ] ] ){
      ++fptr[ i + 1 ];
    }
  }
  bptr[ A.size() ] = B.size() - 1;
  for( int i = A.size(); i > 0; --i ){
    bptr[ i - 1 ] = bptr[ i ];
    if( A[ i - 1 ] == B[ bptr[ i ] ] ){
      --bptr[ i - 1 ];
    }
  }
  for( int i = 0; i <= A.size(); ++i ){ // split point
    if( upmin( minkill, bptr[ i ] - fptr[ i ] + 1 ) ){
      if( minkill <= 0 ){
        cout << B << endl;
        exit( 0 );
      }
      ans = B.substr( 0, fptr[ i ] ) + B.substr( bptr[ i ] + 1 );
    }
  }
}

void solve(){
  cout << ans << endl;
}