| 
文字列sのsubstringと文字列tのsubsequenceが一致するようなものの個数を求める問題。長さはどちらも5000以内。
あとでできてる人のコードや解説を見て。
dp[i][j] = s[i]で終わるsubstringとt[j]以前の文字列のsubsequenceのうち内容が一致するものの個数
とすると、dp[i][j]はt[j]以前のsubsequenceのうちt[j]を使う場合と使わない場合に分けて考えることができる。
t[j]を使わない場合、使わないということはt[j-1]以前の文字列に対するsubsequenceなのでdp[i][j-1]を加算
t[j]を使う場合、s[i]とt[j]を両方使うことになる。
s[i]!=t[j]のときは前に何がきても一致しないので加算なし
s[i]==t[j]のときは s[i-1] でおわるsubstringとt[j-1]以前のsubsequenceが一致すればよいのでdp[i-1][j-1]、
それに加えてs[i]とt[j]一文字だけの場合があるのでさらに1を加算。
というわけで式は
dp[i][j] = dp[i][j-1] + (s[i]==t[j] ? 1+dp[i-1][j-1] : 0)
となる
答えはsubstringが終わるすべての位置について足せばいいのでΣi dp[i][t.size-1]
.....と、言われると納得するけど思いつかんのだなぁ。
本番中はs[i]以前のsubstringとt[j]以前のsubsequenceでずっと考えてて、なんか4通りあるしさらに重複してそうとなってできなかった。
しばらく考えてできないときは状態をもっと分割してみて最後に足す、というアプローチが使えるかも。
(↓あとで通したやつ)
#define MOD 1000000007LL int main() { string A,B; cin>>A>>B; VVI dp(A.size()+1, VI(B.size()+1, 0)); for(int i=1; i<A.size()+1; i++) for(int j=1; j<B.size()+1; j++) { dp[i][j] = ((ll)dp[i][j-1] + (A[i-1]==B[j-1] ? 1+dp[i-1][j-1]:0)) % MOD; } ll ans = 0; REP(i, A.size()+1) ans = (ans+dp[i][B.size()])%MOD; cout<<ans<<endl; return 0; }
