CFR Educational 17 C. Two strings ( Ad hoc )
題意:
給字串 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; }