Pagini recente » Rezultatele filtrării | Rezultatele filtrării | Rezultatele filtrării | Cod sursa (job #1878096) | Cod sursa (job #218137)
Cod sursa(job #218137)
#include <fstream>
#include <string>
using namespace std;
ifstream fin ("adn.in");
ofstream fout ("adn.out");
char s[20][30010];
int n;
char rez[60000];
char sol[60000];
int viz[22];
int d[30010];
void pre(char s[])
{
d[1]=0;
int k=0,n=strlen(s);
for (int i=2;i<n;i++)
{
while (k && s[k+1]!=s[i])
k=d[k];
if (s[k+1]==s[i])
k++;
d[i]=k;
}
}
void kmp(char sol[600000],char s[600000])
{
int n=strlen(sol);
int m=strlen(s);
int k=0;
for (int i=1;i<n;i++)
{
while (k && s[k+1]!=sol[i])
k=d[k];
if (s[k+1]==sol[i])
k++;
if (k==m)
{
return ;
k=d[k];
}
}
for (int i=k+1;i<m;i++)
sol[n++]=s[i];
}
void back(int k)
{
if (k==n)
{
if (strlen(rez)==0)
{
strcpy(rez,sol);
return ;
}
if (strlen(sol)<strlen(rez))
{
memset(rez,0,sizeof(rez));
strcpy(rez,sol);
}
else
if (strlen(sol)==strlen(rez))
if (strcmp(sol,rez)<0)
{
memset(rez,0,sizeof(rez));
strcpy(rez,sol);
}
return ;
}
for (int i=1;i<=n;i++)
if (!viz[i])
{
viz[i]=1;
pre(s[i]);
char aux[60000];
aux[0]=0;
strcpy(aux,sol);
kmp(sol,s[i]);
back(k+1);
viz[i]=0;
memset(sol,0,sizeof(sol));
strcpy(sol,aux);
}
}
void citire()
{
fin>>n;
char c;
int nr;
fin.get(c);
for (int i=1;i<=n;i++)
{
s[i][0]='-';
nr=1;
fin.get(c);
while (c!='\n')
{
s[i][nr++]=c;
fin.get(c);
}
}
}
int main ()
{
citire();
back(0);
fout<<rez;
return 0;
}