CFR 494 B. Obsessive String ( DP, Hash )

Problem - B - Codeforces

題意：
給兩個字串 S 和 T，求有多少種相異的 S 的不重疊子字串集合 ( 集合中任一個子字串有不同的左右界即屬於相異 )，滿足集合裡所有子字串含 T 為子字串，模上 1e9 + 7。

資料規模：
1 ≤ |s|, |t| ≤ 1e5
TL: 2000 ms
ML: 256 MB

解法：
先用 hash 預處理 S 的每個下標是否為和 T 相等的子字串的右界。
很顯然是 DP，轉移到目前的下標 i，需要的資訊是 [ x, i ] 含 T 為子字串的最大 x，以及不超過 x 的所有下標的 dp 值。
這個 x 顯然單調遞增，有上面的預處理就能輕鬆解決。
考慮 dp 轉移式：
dp[ i ]：已考慮前 i 個字符，且其中一個子字串含 S[ i - 1 ]，此時相異 S[ 0, i ) 的不重疊子字串集合方案數模上 1e9 + 7
dp[ i ] = Sigma{ Sigma{ dp[ a ], for all 0 ≤ a ≤ b }, for all 0 ≤ b ≤ x, where x is the largest integer that satisfies S[ x, x + | T | ) = T }
因為 S[ i - 1 ] 必須取，所以最後一個字串可以是 S[ t, i ), for any 0 ≤ t ≤ x，而當最後一個字串取的是 S[ t, i )，方案數是 dp[ t ]。所以要對 dp 表做兩層的前綴和加速。

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

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

string S, T;

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

const int BASE = 301;
const int HS = 2; // hash size
const int MOD[] = { ( int ) 1e9 + 7, ( int ) 1e9 + 9 };

vi phash[ HS ];
vi pbase[ HS ];
int thv[ HS ]; // hash value of T
vi jump;

void preprocess(){
  for( int t = 0; t < HS; ++t ){
    phash[ t ] = pbase[ t ] = vi( S.size() + 1 );
    pbase[ t ][ 0 ] = 1;
    for( int i = 0; i < S.size(); ++i ){
      phash[ t ][ i + 1 ] = ( 1LL * phash[ t ][ i ] * BASE + S[ i ] ) % MOD[ t ];
      pbase[ t ][ i + 1 ] = 1LL * pbase[ t ][ i ] * BASE % MOD[ t ];
    }
  }
  for( int t = 0; t < HS; ++t ){
    for( int i = 0; i < T.size(); ++i ){
      thv[ t ] = ( 1LL * thv[ t ] * BASE + T[ i ] ) % MOD[ t ];
    }
  }
  jump = vi( S.size() + 1, -1 );
  for( int i = 0; i + T.size() <= S.size(); ++i ){
    int ng = 0;
    for( int t = 0; t < HS; ++t ){
      int shv = ( phash[ t ][ i + T.size() ] - 1LL * pbase[ t ][ T.size() ] * phash[ t ][ i ] % MOD[ t ] ) % MOD[ t ];
      if( shv < 0 ) shv += MOD[ t ];
      ng |= shv != thv[ t ];
    }
    if( ng ) continue;
    jump[ i + T.size() ] = i;
  }
}

vi dp;
vi pdp;
vi ppdp;

void solve(){
  ppdp = pdp = dp = vi( S.size() + 1 );
  ppdp[ 0 ] = pdp[ 0 ] = dp[ 0 ] = 1;
  int last_jump = -1;
  for( int i = 0; i < S.size(); ++i ){
    if( jump[ i + 1 ] != -1 ){
      last_jump = jump[ i + 1 ];
      ( dp[ i + 1 ] += pdp[ jump[ i + 1 ] ] + jump[ i + 1 ] ) %= MOD7;
    }
    if( last_jump != -1 ){
      dp[ i + 1 ] = ppdp[ last_jump ];
    }
    pdp[ i + 1 ] = ( pdp[ i ] + dp[ i + 1 ] ) % MOD7;
    ppdp[ i + 1 ] = ( ppdp[ i ] + pdp[ i + 1 ] ) % MOD7;
  }
  int ans = pdp[ S.size() ] - pdp[ 0 ];
  if( ans < 0 ) ans += MOD7;
  cout << ans << endl;
}