#include #define MAX 100 /* sizeof(Hell) */ #define INF 100000 /* Nekonečno */ char a[MAX], b[MAX]; /* Satanovy řetězce, tradičně ukončené kódem 0 */ int opt[MAX][MAX]; /* Optimální délka řetězce pro danou dvojici suffixů SP */ int optx[MAX][MAX], opty[MAX][MAX]; /* Poznámky ke~konstrukci řetězců */ char optc[MAX][MAX]; int D(int x, int y) /* Spočte funkci D pro zadané suffixy SP */ { int ret; /* Budoucí výsledek */ int bx=0, by=0; /* Odkud jsme ho vzali */ int bc=0; /* A co musíme připsat do výstupu, aby vznikl */ if (opt[x][y] >= 0) /* Králík z~klobouku? */ return opt[x][y]; /* Dvě pomocná makra: nastavení výsledku a pokus o~jeho vylepšení */ #define SET(xx,yy,cc) do { ret=D(xx,yy); bx=xx; by=yy; bc=cc; } while(0) #define UPDATE(xx,yy,cc) do { int r2=D(xx,yy); if (r2 < ret) { ret=r2; bx=xx; by=yy; bc=cc; } } while(0) if (!a[x] && !b[y]) /* Oba řetězce skončily */ ret = 0; else if (a[x] == '*' && b[y] == '*') { /* Dvě hvězdičky */ SET(x+1,y,0); UPDATE(x,y+1,0); } else if (a[x] == '*') { /* Hvězdička vlevo \dots\ */ SET(x+1,y,0); if (b[y]) UPDATE(x,y+1,b[y]); } else if (b[y] == '*') { /* \dots\ nebo vpravo */ SET(x,y+1,0); if (a[x]) UPDATE(x+1,y,a[x]); } else if (a[x] == b[y]) /* 2 stejné znaky */ SET(x+1,y+1,a[x]); else if (a[x] == '?' && b[y]) /* Otazníky */ SET(x+1,y+1,b[y]); else if (a[x] && b[y] == '?') SET(x+1,y+1,a[x]); else /* Jinak nemožno */ ret = INF; optx[x][y] = bx; opty[x][y] = by; optc[x][y] = bc; return opt[x][y] = ret; } int main(void) { int i,j,l; scanf("%s%s", a, b); for (i=0; i= INF) { printf("Pomooooc! Prohraavaaaaam!\n"); return 0; } int x=0, y=0, nx; /* Rekonstrukce výsledného řetězce */ while (a[x] && b[y]) { if (optc[x][y]) putchar(optc[x][y] == '?' ? 'x' : optc[x][y]); nx = optx[x][y]; y = opty[x][y]; x = nx; } putchar('\n'); return 0; }