# CFR 494 B. Obsessive String ( DP, Hash )

Problem - B - Codeforces

1 ≤ |s|, |t| ≤ 1e5
TL: 2000 ms
ML: 256 MB

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 }

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;
}
```