Cod sursa(job #30695)

Utilizator buradaandreiBurada Andrei buradaandrei Data 14 martie 2007 21:30:49
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <fstream.h>
#include <string.h>
int n,ve[18]={-1},con=0;
char aux[30001];
ifstream f("adn.in");
ofstream g("adn.out");
struct co
	{
	co *next;
	int care,unde,cat;
	};
co *p,*u;
int luat(int x)
{
int i;
for (i=0;i<con;i++)
	if (ve[i]==x) return 1;
return 0;
}
void add_i(co *&p, int ca, int un, int ma)
{
co *c=new co;
c->care=ca;
c->unde=un;
c->cat=ma;
c->next=p;
p=c;
}
void add_d(co *&p, co *&u, int ca, int un, int ma)
{
if (!p)
	{
	p=new co;
	p->care=ca;
	p->unde=un;
	p->cat=ma;
	p->next=NULL;
	u=p;
	}
else
	{
	co *c=new co;
	c->care=ca;
	c->unde=un;
	c->cat=ma;
	c->next=NULL;
	u->next=c;
	u=c;
	}
}
void sterg(int x)
{
if (p->care==x)
	{
	co *aux=p;
	p=p->next;
	delete aux;
	}
else if (u->care==x)
	{
	co *c=p;
	while (c->next!=u) c=c->next;
	delete u;
	u=c;
	}
}
void concatenare(int ca, int un, int ma)
{
if (un==1) add_i(p,ca,un,ma);
else add_d(p,u,ca,un,ma);
}
int main()
{
char *secv[3000];
int cat,unde,care,max,i,j;
f>>n;
for (i=0;i<n;i++)
	{
	f>>aux;
	secv[i]=new char[strlen(aux)+1];
	strcpy(secv[i],aux);
	}
/*for (i=0;i<n;i++)
	g<<secv[i]<<"\n";*/
add_d(p,u,0,2,strlen(secv[0]));
ve[con++]=0;
i=0;
int n2=n;
while (n2-1)
//for (i=n-1;i>=0;i--)
//	if (!luat(i))
	{
	max=0;
	for (j=0;j<=n-1;j++)
		if (!luat(j)&&j!=i)
		{
			int l1=strlen(secv[i]);
			int l2=strlen(secv[j]);
			int k=-1,l=-1;
			int cats=0,catd=0;
			while (k<l1-1&&l<l2-1)
				{
				k++;
				l++;
				if (secv[i][k]==secv[j][l]) catd++;
				else
					{
					if (catd!=0) k--;
					catd=0;
					l=-1;
					}
				}
			k=-1;l=-1;
			while (k<l1-1&&l<l2-1)
				{
				k++;
				l++;
				if (secv[i][k]==secv[j][l]) cats++;
				else
					{
					if (cats!=0) l--;
					cats=0;
					k=-1;
					}
				}
			if (catd>max) {max=catd;unde=2;care=j;}
			if (cats>max) {max=cats;unde=1;care=j;}
		}
	n2--;
	ve[con++]=care;
	if (max==strlen(secv[i])) {max=strlen(secv[care]);unde=2;sterg(i);}
	i=care;
	concatenare(care,unde,max);
	}
co *v=p;
while (v)
	{
	if (v->unde==1)
		for (i=0;i<(strlen(secv[v->care])-v->cat);i++)
			g<<secv[v->care][i];
	else
		for (i=(strlen(secv[v->care])-v->cat);i<strlen(secv[v->care]);i++)
			g<<secv[v->care][i];
	v=v->next;
	}
f.close();
g.close();
return 0;
}