Cod sursa(job #318455)

Utilizator GulosSerban Petrescu Gulos Data 28 mai 2009 15:57:57
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include<iostream>
#include<fstream>
#include<string>

using namespace std;

int bs (char a[],char b[]){
	int s,d,m,n;
	char *p,*t;
	p=&b[0];
	s=0;n=d=strlen(a);
	do{
		m=(s+d)/2;
		t=strstr(b,a+m);
		if (t!=0){
			if (((int)(t-p)<m)){
				if (strncmp(a+m-(int)(t-p),b,n-m+(int)(t-p))==0)
					return (n-m+(int)(t-p));
				else
					d=m-1;
			}
			else
				s=m+1;
		}
		else
			s=m+1;
	}while (s<=d);
	return 0;
}

int main(){
	ifstream fin("adn.in");
	ofstream fout("adn.out");
	char s[19][3005];
	int n;
	fin>>n;fin.get();
	int i,j,c;
	for (i=0;i<n;i++){
		fin.get(s[i],3001,'\n');
		fin.get();
	}
	char *a;
	int m[20][20];
	for (i=0;i<n;i++)
		for (j=0;j<n;j++)
			if (j!=i){
				a=strstr(s[i],s[j]);
				if (a!=0)
					s[j][0]=0;
			}
	for (i=0;i<n;i++)
		if (s[i][0]!=0)
			for (j=0;j<n;j++)
				if (s[j][0]!=0)
					if (i!=j)
						m[i][j]=bs(s[i],s[j]);
	int max,in,min=200000000;
	for (i=0;i<n;i++){
		if (s[i][0]!=0){
			max=-1;
			for (j=0;j<n;j++)
				if (m[j][i]>max)
					max=m[j][i];
			if (max<min){
				min=max;
				in=i;
			}
		}
	}
	max=0;
	for (i=0;i<n;i++)
		if (s[i][0]!=0)
			max++;
	c=0;
	do{
		fout<<s[in]+c;
		max--;
		c=-1;
		for (i=0;i<n;i++){
			if (in!=i)
				if (m[in][i]>c){
					c=m[in][i];
					j=i;
				}
		}
		in=j;
	}while(max);
}