Pagini recente » Cod sursa (job #773921) | Cod sursa (job #725968) | Cod sursa (job #1386869) | Cod sursa (job #2196043) | Cod sursa (job #1490253)
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
using namespace std;
string s[18];
bool b[18];
int t[18][18];
int best=0;
int best_sorrend[18];
int n;
void tovabblep (int most, int sum, int sorrend[], int counter)
{
bool goon=false;
for (int i=0;i<n;i++)
{
if (b[i] and i!=most)
{
goon=true;
}
}
if(goon)
{
for (int i=0;i<n;i++)
{
if (i!=most and b[i] and t[most][i]>0)
{
sorrend[counter]=most;
b[most]=false;
tovabblep(i,sum+t[most][i], sorrend, counter+1);
b[most]=true;
}
}
}
else
{
if (sum>best)
{
best=sum;
for (int i=0;i<n;i++)
{
best_sorrend[i]=sorrend[i];
}
best_sorrend[counter]=most;
}
}
}
int main()
{
ifstream be("ADN.in");
ofstream ki("ADN.out");
be>>n;
int biggest_nr;
int sorrend[18];
getline(be,s[0]);
for (int i=0;i<n;i++)
{
b[i]=true;
sorrend[i]=-1;
getline(be,s[i]);
}
best_sorrend[n]=-1;
for (int i=0;i<n;i++)
{
for (int pp=0;pp<n;pp++)
{
biggest_nr=pp;
if (s[i].size()<=s[biggest_nr].size() and i!=biggest_nr and b[biggest_nr]==true)
{
for (int j=0;j<s[biggest_nr].size();j++)
{
if (s[i].size()>s[biggest_nr].size()-j)
{
break;
}
if (s[biggest_nr][j]==s[i][0])
{
bool reszhalmaz=true;
for (int p=0;p<s[i].size();p++)
{
if (s[i][p]!=s[biggest_nr][j+p])
{
reszhalmaz=false;
break;
}
}
if (reszhalmaz)
{
b[i]=false;
}
}
}
}
}
}
/*for (int i=0;i<n;i++)
{
cout<<b[i];
}*/
for (int i=0;i<n;i++)
{
t[i][i]=-1;
}
for (int i=0;i<n;i++)
{
if (b[i])
{
for (int j=0;j<n;j++)
{
if (i!=j and b[j])
{
bool talal;
int q=0;
while(q<s[i].size() and q<s[j].size())
{
talal=true;
for (int p=0;p<=q;p++)
{
if (s[i][s[i].size()-1-q+p]!=s[j][p])
{
talal=false;
}
}
if (talal)
{
t[i][j]=q+1;
}
q++;
}
}
}
}
}
/*cout<<endl;
for (int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
{
if (t[i][j]==-1)
{
cout<<setw(3)<<" ";
}
else
cout<<setw(3)<<t[i][j]<<" ";
}
cout<<endl;
}*/
for (int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
{
if (i!=j and b[i] and b[j] and t[i][j]>0)
{
sorrend[0]=i;
b[i]=false;
tovabblep( j, t[i][j], sorrend, 1);
b[i]=true;
}
}
}
int i=1;
ki<<s[best_sorrend[0]];
while (best_sorrend[i]!=-1)
{
for (int j=t[best_sorrend[i-1]][best_sorrend[i]];j<s[best_sorrend[i]].size();j++)
{
ki<<s[best_sorrend[i]][j];
}
i++;
}
return 0;
}