[AOJ] No. 0341 繰り返す呪文

2019年12月27日2020年12月18日

問題

方針

動的計画法を行います。\( d(i, j) \) を \( t \) の \( j \) 番目までの部分文字列において、\( b \) の \( j \) 番目までの部分文字列の出現回数とします。初期値は、\( d(i, 0) = 1 \ ( 0 \leq i \leq |t|) \) とします。更新式は以下となります。

• \( t_i = b_j \) のとき

\[d(i + 1, j + 1) = d(i, j + 1) + d(i, j)\]

• \( t_i \neq b_j \) のとき

\[d(i + 1, j + 1) = d(i, j + 1)\]

\( d(|t|, |b|) \) が答えとなります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    string t, b;
    cin >> t >> b;
    if (t.length() < b.length()) {
        cout << "0\n";
        return 0;
    }
    ll mod = 1000000007;
    int n = t.length();
    int m = b.length();
    ll d[n + 1][m + 1]{};
    // d[i][j] 部分文字列t[1..i]において、部分文字列b[1..j]が現れた回数
    d[0][0] = 1;
    for (int i = 0; i <= n; i++) {
        d[i][0] = 1;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (t[i] == b[j]) {
                d[i + 1][j + 1] = (d[i][j + 1] + d[i][j]) % mod;;
            } else {
                d[i + 1][j + 1] = d[i][j + 1];
            }
        }
    }
    // for (int i = 0; i <= n; i++) {
    //     for (int j = 0; j <= m; j++) {
    //         cout << d[i][j] << " ";
    //     }
    //     cout << "\n";
    // }
    cout << d[n][m] << "\n";
    return 0;
}