Cod sursa(job #1850055)

Utilizator NineshadowCarapcea Antonio Nineshadow Data 18 ianuarie 2017 09:33:33
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("adn.in");
ofstream out("adn.out");
typedef struct link link_t;
struct link {
	int len;
	char letter;
	link_t *next;
};
int scs(char *x, char *y, char *out)
{
	int lx = strlen(x), ly = strlen(y);
	link_t lnk[ly + 1][lx + 1];

	for (int i = 0; i < ly; i++)
		lnk[i][lx] = (link_t) {ly - i, y[i], &lnk[i + 1][lx]};

	for (int j = 0; j < lx; j++)
		lnk[ly][j] = (link_t) {lx - j, x[j], &lnk[ly][j + 1]};

	lnk[ly][lx] = (link_t) {0};

	for (int i = ly; i--; ) {
		for (int j = lx; j--; ) {
			link_t *lp = &lnk[i][j];
			if (y[i] == x[j]) {
				lp->next = &lnk[i+1][j+1];
				lp->letter = x[j];
			} else if (lnk[i][j+1].len < lnk[i+1][j].len) {
				lp->next = &lnk[i][j+1];
				lp->letter = x[j];
			} else {
				lp->next = &lnk[i+1][j];
				lp->letter = y[i];
			}
			lp->len = lp->next->len + 1;
		}
	}

	for (link_t *lp = &lnk[0][0]; lp; lp = lp->next)
		*out++ = lp->letter;

	return 0;
}
int n;
char x[300001],y[300001],res[3000001];
int main(void)
{
    in>>n;
    in.ignore();
    in.getline(x,300001);
    n--;
    while(n--){
    in.getline(y,300001);
	scs(x, y, res);
	memcpy(x,res,300001);
    }
	out<<res;
	return 0;
}