/*------------------------------------------------------------------------------
 * dna.c: align two dna sequeunces
**----------------------------------------------------------------------------*/

/* Copyright (c) 2009 Peter Bui. All Rights Reserved.
 *
 * Peter Bui <pbui@cse.nd.edu>
 *
**------------------------------------------------------------------------------
 * Includes
**----------------------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*------------------------------------------------------------------------------
 * Constants
**----------------------------------------------------------------------------*/

#define TRUE	    1
#define FALSE	    0

#define MAX_SEQLEN 20

/*------------------------------------------------------------------------------
 * Global Variables
**----------------------------------------------------------------------------*/

static int ST[MAX_SEQLEN + 1][MAX_SEQLEN + 1]; // Sequence Table

/*------------------------------------------------------------------------------
 * Functions
**----------------------------------------------------------------------------*/


static void
print_table(int slen1, int slen2)
{
    int r, c;

    for (r = 0; r <= slen2; r++) {
	for (c = 0; c <= slen1; c++) 
	    putchar(ST[r][c] + '0');
	putchar('\n');
    }
}

/*----------------------------------------------------------------------------*/

static int
max(int a, int b, int c) 
{
    int t = ((a > b) ? a : b);
    return ((t > c) ? t : c);
}

/*----------------------------------------------------------------------------*/

static void
compute_alignment(char *s1, char *s2)
{
    int r, c, slen1, slen2;

    memset(ST, 0, sizeof(int) * (MAX_SEQLEN + 1) * (MAX_SEQLEN + 1));

    slen1 = strlen(&s1[1]);
    slen2 = strlen(&s2[1]);

    for (r = 1; r <= slen2; r++) 
	for (c = 1; c <= slen1; c++) 
	    ST[r][c] = max(ST[r - 1][c - 1] + (s1[c] == s2[r]), ST[r][c - 1], ST[r - 1][c]);
}

/*----------------------------------------------------------------------------*/

static void
print_alignment(char *s1, char *s2)
{
    char  sa[MAX_SEQLEN + 1];
    char *sp;
    int r, c, m;

    memset(sa, 0, sizeof(char) * (MAX_SEQLEN + 1));
    
    r  = strlen(&s2[1]);
    c  = strlen(&s1[1]);
    sp = &sa[c];

    while (r > 0 && c > 0) {
	if (s1[c] == s2[r]) {
	    *sp-- = s1[c];
	    r--;
	    c--;
	} else {
	    *sp-- = '_';
	    c--;
	}
    }

    while (sp >= sa)
	*sp-- = '_';

    puts(&s1[1]);
    puts(&sa[1]);
}

/*------------------------------------------------------------------------------
 * Main Execution
**----------------------------------------------------------------------------*/

int
main(int argc, char* argv[]) 
{
    char s1[MAX_SEQLEN + 1];
    char s2[MAX_SEQLEN + 1];

    while (scanf("%s %s", &s1[1], &s2[1]) != EOF) {
	compute_alignment(s1, s2);
	print_alignment(s1, s2);
    }

    return (EXIT_SUCCESS);
}

/*------------------------------------------------------------------------------
 * vim: sts=4 sw=4 ts=8 ft=c
**----------------------------------------------------------------------------*/