Pagini recente » Cod sursa (job #2152798) | Cod sursa (job #214534) | Cod sursa (job #1628993) | Cod sursa (job #816636) | Cod sursa (job #3170552)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 502;
int n,m,dp[NMAX][NMAX][NMAX];
string a,b;
ifstream fin("iv.in");
ofstream fout("iv.out");
int main()
{
fin >> a >> b;
n = a.size(), m = b.size();
a = "$"+a;
b = "$"+b;
dp[0][0][0] = 1;
int half = (n+m)/2;
for(int i = 1; i <= (n+m)/2; i++){
for(int p1 = 0; p1 <= n && p1 <= i; p1++){
for(int q1 = 0; p1+q1 <= n && q1 <= i; q1++){
int p2 = i-p1;
int q2 = i-q1;
if(a[p1] == a[n-q1+1]){
dp[i][p1][q1] += dp[i-1][p1-1][q1-1];
}
if(a[p1] == b[m-q2+1]){
dp[i][p1][q1] += dp[i-1][p1-1][q1];
}
if(b[p2] == a[n-q1+1]){
dp[i][p1][q1] += dp[i-1][p1][q1-1];
}
if(b[p2] == b[m-q2+1]){
dp[i][p1][q1] += dp[i-1][p1][q1];
}
}
}
}
int ans = 0;
if((n+m)%2 == 0){
for(int i = 0; i <= n; i++){
ans += dp[half][i][n-i];
}
}else{
for(int i = 0; i <= n; i++){
ans += dp[half][i][n-i-1] + dp[half][i][n-i];
}
}
fout << ans;
return 0;
}