Pagini recente » Cod sursa (job #979465) | Cod sursa (job #1096653) | Cod sursa (job #257619) | Cod sursa (job #1866999) | Cod sursa (job #2719283)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("adn.in");
ofstream fout ("adn.out");
int dp[(1<<18)][20],pre[(1<<18)][20],l[20],pi[20][30005],in[20],c[20][20];
char s[20][30005];
void prefix (int ind)
{
int now=0,i;
for (i=2;i<=l[ind];i++)
{
now=pi[ind][i-1];
while (now && s[ind][i]!=s[ind][now+1])
now=pi[ind][now];
if (s[ind][i]==s[ind][now+1])
now++;
pi[ind][i]=now;
}
}
int kmp (int x,int y)
{
int now=0,i;
for (i=1;i<=l[x];i++)
{
while (now && s[x][i]!=s[y][now+1])
now=pi[y][now];
if (s[x][i]==s[y][now+1])
now++;
if (now==l[y])
return l[y];
}
return now;
}
void atrb (int i,int j)
{
if (kmp(i,j)==l[j])
in[j]=1;
else
c[i][j]=-kmp(i,j);
}
void recon (int mask,int p)
{
if (mask==(1<<p))
{
fout<<s[p]+1;
return;
}
recon(mask^(1<<p),pre[mask][p]);
fout<<(s[p]+1-c[pre[mask][p]][p]);
}
int main()
{
int n,f=0,i,j,ans=200000000,last,mask;
fin>>n;
for (i=0;i<n;i++)
for (j=0;j<(1<<n);j++)
dp[j][i]=200000000;
for (i=0;i<n;i++)
{
fin>>(s[i]+1);
l[i]=strlen(s[i]+1);
prefix(i);
}
for (i=0;i<n;i++)
for (j=i+1;j<n;j++)
{
atrb(i,j);
atrb(j,i);
}
for (i=0;i<n;i++)
if (!in[i])
{
f+=(1<<i);
dp[(1<<i)][i]=0;
}
for (mask=1;mask<(1<<n);mask++)
for (i=0;i<n;i++)
if (mask&(1<<i) && !in[i])
for (j=0;j<n;j++)
if (i!=j && !in[j] && mask&(1<<j) && dp[mask][i]>dp[mask^(1<<i)][j]+c[j][i])
{
dp[mask][i]=min(dp[mask][i],dp[mask^(1<<i)][j]+c[j][i]);
pre[mask][i]=j;
}
for (i=0;i<n;i++)
if (dp[f][i]<ans)
{
ans=dp[f][i];
last=i;
}
recon(f,last);
return 0;
}