Pagini recente » Cod sursa (job #3201794) | Cod sursa (job #1302378) | Cod sursa (job #1673035) | Cod sursa (job #912806) | Cod sursa (job #1850055)
#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;
}