Pagini recente » Cod sursa (job #1282282) | Cod sursa (job #2455780) | Cod sursa (job #2509524) | Cod sursa (job #2848149) | Cod sursa (job #3250546)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
const string FILE_NAME = "iv";
const int MAX_N = 500;
int dp[MAX_N + 5][MAX_N + 5][MAX_N + 5];
int main () {
#ifndef LOCAL
ifstream cin(FILE_NAME + ".in");
ofstream cout(FILE_NAME + ".out");
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int len, n, m, st1, st2, dr1, dr2, ans;
string a, b;
cin >> a >> b;
n = a.size();
m = b.size();
// index 1
a = '#' + a;
b = '#' + b;
dp[0][0][0] = 1;
for (len = 1; len <= (n + m) / 2; len++) {
for (st1 = 0; st1 <= min(len, n); st1++) {
for (dr1 = 0; dr1 <= min(len, n - st1); dr1++) {
st2 = len - st1;
dr2 = len - dr1;
if (a[st1] == a[n - dr1 + 1]) {
dp[len][st1][dr1] += dp[len - 1][st1 - 1][dr1 - 1];
}
if (b[st2] == b[m - dr2 + 1]) {
dp[len][st1][dr1] += dp[len - 1][st1][dr1];
}
if (a[st1] == b[m - dr2 + 1]) {
dp[len][st1][dr1] += dp[len - 1][st1 - 1][dr1];
}
if (b[st2] == a[n - dr1 + 1]) {
dp[len][st1][dr1] += dp[len - 1][st1][dr1 - 1];
}
}
}
}
ans = 0;
for (st1 = 0; st1 <= n; st1++) {
dr1 = n - st1;
ans += dp[(n + m) / 2][st1][dr1];
}
if ((n + m) & 1) {
for (st1 = 0; st1 <= n; st1++) {
dr1 = n - st1 - 1;
ans += dp[(n + m) / 2][st1][dr1];
}
}
cout << ans << "\n";
return 0;
}