CFR 163 A. Substring and Subsequence ( DP, String )

Problem - A - Codeforces

題意：
給字串 S 和 T，要求有多少組 ( a, b, c, d )，使得 S[ a, b ) 和 T[ c, d ) 非空且 LCS 為 S[ a, b )。

資料規模：
字串長度不超過 5000
TL: 1000 ms
ML: 256 MB

解法：
dp[ i ][ j ]：滿足 LCS( S[ x, i ), T[ y, j ) ) == S[ x, i ) 的 ( x, y ) 數量
考慮如何轉移：
if S[ i ] == T[ j ]：
__dp[ i + 1 ][ j + 1 ] += dp[ i ][ j ] + 1 // 以 i, j 為各自的右界，+1 是指 ( i, i + 1, j, j + 1 ) 的方案。
dp[ i ][ j + 1 ] += dp[ i ][ j ]：( i, j ) 有幾種方案，後面都添上 T[ j ] 就讓 ( i, j + 1 ) 多幾種。
答案為 Sigma{ dp[ i ][ T.size() ], for all i }

時間 / 空間複雜度：
O( | S | * | T | )

const int MOD7 = ( int ) 1e9 + 7;

string S, T;

void init(){
  cin >> S >> T;
}

vvi dp;

void preprocess(){
  dp = vvi( S.size() + 1, vi( T.size() + 1 ) );
  for( int i = 0; i <= S.size(); ++i ){
    for( int j = 0; j <= T.size(); ++j ){
      if( i + 1 <= S.size() and j + 1 <= T.size() and S[ i ] == T[ j ] ){
        ( dp[ i + 1 ][ j + 1 ] += dp[ i ][ j ] + 1 ) %= MOD7;
      }
      if( j + 1 <= T.size() ){
        ( dp[ i ][ j + 1 ] += dp[ i ][ j ] ) %= MOD7;
      }
    }
  }
}

void solve(){
  int ans = 0;
  for( int i = 1; i <= S.size(); ++i ){
    ( ans += dp[ i ][ T.size() ] ) %= MOD7;
  }
  cout << ans << endl;
}