Baekjoon #2602

#include<bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    string S, bridge[2]; cin >> S >> bridge[0] >> bridge[1];
    int N = (int)bridge[0].size();
    int K = (int)S.size();

    // DP[2][N][K]
    vector<vector<vector<int>>> DP(2, vector<vector<int>>(N + 1, vector<int>(K + 1)));

    DP[0][0][0] = DP[1][0][0] = 1;
    for(int i = 1; i <= N; ++i) {
        for(int k = 0; k < 2; ++k) {
            char ch = bridge[k][i - 1];
            for(int l = 1; l <= K; ++l) {
                if(S[l - 1] != ch) continue;
                for(int j = 0; j < i; ++j) {
                    DP[k][i][l] += DP[1 - k][j][l - 1];
                }
            }
        }
    }

    int ans = 0;
    for(int i = 1; i <= N; ++i) {
        ans += DP[0][i][K] + DP[1][i][K];
    }
    cout << ans;
    
    return 0;
}