CFR 615 C. Running Track ( LCP, DP )

Problem - 615C - Codeforces

題意：
給 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;
  }
}