Pagini recente » Cod sursa (job #2446971) | Cod sursa (job #1369585) | Cod sursa (job #1999690) | Cod sursa (job #2433728) | Cod sursa (job #2433860)
#include<iostream>
#include<string>
#include<fstream>
#include<vector>
using namespace std;
ifstream in("adn.in");
ofstream out("adn.out");
string string_list[18];
int strings=0;
bool used[18] {false};
void read()
{
in>>strings;
for(int i=0; i<strings; i++)
{
in>>string_list[i];
}
}
void compute_lsp(int*lsp_array,string to_compute)
{
int i=1,l=0;
lsp_array[0]=0;
while(i<to_compute.length())
{
if(to_compute[i]==to_compute[l])
{
l++;
lsp_array[i]=l;
i++;
}
else
{
if(l!=0)
{
l=lsp_array[l-1];
}
else
{
lsp_array[i]=0;
i++;
}
}
}
}
string kmp(string main,string pattern)
{
int lsp[pattern.length()];
compute_lsp(lsp,pattern);
int i=0,p=0;
while(i<main.length())
{
if(main[i]==pattern[p])
{
i++;
p++;
}
if(p==pattern.length())
{
p=lsp[p-1];
}
if(i<main.length() &&main[i]!=pattern[p])
{
if(p!=0)
{
p=lsp[p-1];
}
else
i++;
}
}
return main.substr(0,main.length()-p)+pattern;
}
string result="";
void backtrack(int current_depth,string merged)
{
if(current_depth==strings)
{
if(result=="" || result.length()>merged.length())
result=merged;
return;
}
for(int i=0; i<strings; i++)
{
if(!used[i])
{
used[i]=true;
backtrack(current_depth+1,kmp(merged,string_list[i]));
used[i]=false;
}
}
}
int main()
{
read();
backtrack(0,"");
out<<result;
return 0;
}