CFR 615 C. Running Track ( LCP, DP )
題意:
給 A 字串和 B 字串,可以將 A 字串中的子字串剪下來,選擇要不要翻轉後,接到當前的字串後面。問最少操作數能否接成 B,要輸出方案。
解法:
首先顯然從左到右掃過 B 字串,每次貪心選取最長且合法的子字串接上。
考慮最長公共前綴 :
lcp[ i ][ j ]:以 A 字串中的下標 i 和 B 字串中的下標 j 各為開頭,此時的最長公共前綴。
對 A 的正逆預處理過後,就能用 O( | A | ) 時間更新最長可移動的長度。
時間 / 空間複雜度:
O( | A | * | B | )
注意:
用 hash 會 TLE = =。寫到崩潰。
string A, B; void init(){ cin >> A >> B; } vvi lcp; vvi rv_lcp; void preprocess(){ lcp = vvi( A.size() + 1, vi( B.size() + 1 ) ); for( int i = A.size(); i > 0; --i ){ for( int j = B.size(); j > 0; --j ){ if( A[ i - 1 ] == B[ j - 1 ] ){ lcp[ i - 1 ][ j - 1 ] = lcp[ i ][ j ] + 1; } } } reverse( A.begin(), A.end() ); rv_lcp = vvi( A.size() + 1, vi( B.size() + 1 ) ); for( int i = A.size(); i > 0; --i ){ for( int j = B.size(); j > 0; --j ){ if( A[ i - 1 ] == B[ j - 1 ] ){ rv_lcp[ i - 1 ][ j - 1 ] = rv_lcp[ i ][ j ] + 1; } } } } void solve(){ vp ans; for( int i = 0; i < B.size(); ){ int max_len = 0, type = -1, idx = -1; for( int j = 0; j < A.size(); ++j ){ if( upmax( max_len, lcp[ j ][ i ] ) ){ type = 0; idx = j; } } for( int j = 0; j < A.size(); ++j ){ if( upmax( max_len, rv_lcp[ j ][ i ] ) ){ type = 1; idx = j; } } if( max_len == 0 ){ cout << -1 << endl; exit( 0 ); } if( type == 0 ){ ans.emplace_back( idx, idx + max_len - 1 ); } else{ ans.emplace_back( A.size() - 1 - idx, A.size() - 1 - ( idx + max_len - 1 ) ); } i += max_len; } cout << ans.size() << endl; for( int i = 0; i < ans.size(); ++i ){ cout << ans[ i ].first + 1 << " " << ans[ i ].second + 1 << endl; } }