Pagini recente » Cod sursa (job #350920) | Cod sursa (job #1268811) | Cod sursa (job #126382) | Cod sursa (job #2756373) | Cod sursa (job #833756)
Cod sursa(job #833756)
#include <stdio.h>
#include <string.h>
int N, M, dp[210][210][210];
char x[510], y[510];
int isNull(int x)
{
if (x == 0)
return -1;
return x;
}
int solve(int x0, int y0, int x1)
{
int y1 = x0 - 1 + x1 - 1 - N + y0;
y1 = M - y1;
if (dp[x0][y0][x1] != -1)
return dp[x0][y0][x1];
if (x0 > y0 || x1 > y1)
return 1;
int ret = 0;
if (x[x0] == x[y0])
ret += solve(x0 + 1, y0 - 1, x1);
if (x[x0] == y[y1])
ret += solve(x0 + 1, y0, x1);
if (y[x1] == x[y0])
ret += solve(x0, y0 - 1, x1 + 1);
if (y[x1] == y[y1])
ret += solve(x0, y0, x1 + 1);
return dp[x0][y0][x1] = ret;
}
int main()
{
int i, j, k;
freopen("iv.in", "r", stdin);
freopen("iv.out", "w", stdout);
gets(x + 1); gets(y + 1);
N = strlen(x + 1); M = strlen(y + 1);
for (i = 0; i <= N; i ++)
for (j = 0; j <= N; j ++)
for (k = 0; k <= M; k ++)
dp[i][j][k] = -1;
printf("%d", solve(1, N, 1));
return 0;
}