Pagini recente » Cod sursa (job #3192048) | Cod sursa (job #969039) | Cod sursa (job #501975) | Cod sursa (job #118104) | Cod sursa (job #1058220)
#include <fstream>
#include <iostream>
using namespace std;
const unsigned int maxl = 30000,
maxn = 18;
int N;
string s[maxn],
stringBuffer,
S = "";
int st[maxn];
inline void read() {
ifstream fileInStream("adn.in");
fileInStream >> N;
for(int i = 0; i < N; i++) {
fileInStream >> s[i];
}
}
inline void write() {
ofstream fileOutStream("adn.out");
fileOutStream << S;
}
bool equals(string &b, unsigned int pos1, unsigned short stringIndex, unsigned int pos2, unsigned int length) {
unsigned int i = pos1;
while(i - pos1 < length) {
if(b[i++] != s[st[stringIndex]][pos2++]) {
return false;
}
}
return true;
}
string process() {
unsigned int x;
string buffer = "";
for(int i = 0; i < N; ++i) {
for(buffer.length() < s[st[i]].length() ? x = buffer.length() : x = s[st[i]].length(); x >= 0; --x) {
if(equals(buffer, buffer.length()-x, i, 0, x)) {
buffer += s[st[i]].substr(x, s[st[i]].length()-x);
break;
}
}
}
return buffer;
}
/*void permute(unsigned int it) {
if(it == N) {
stringBuffer = process();
if(S == "" || stringBuffer.length() < S.length()) {
S = stringBuffer;
}
} else {
for(unsigned int i = 0; i < N; ++i) {
swap(s[i], s[it]);
permute(it+1);
swap(s[i], s[it]);
}
}
}*/
void init(int k) {
st[k] = -1;
}
bool scc(int k) {
if(st[k] < N-1) {
st[k]++;
return true;
}
return false;
}
bool val(int k) {
for(int i = 0; i < k; i++) {
if(st[i] == st[k]) {
return false;
}
}
return true;
}
bool sol(int k) {
return k == N-1;
}
void backtracking() {
int k = 0;
bool e, v;
init(k);
while(k > -1) {
do {
e = scc(k);
if(e) v = val(k);
}while(e && !v);
if(e) {
if(sol(k)) {
stringBuffer = process();
if(S == "" || stringBuffer.length() < S.length()) {
S = stringBuffer;
}
} else {
k++;
init(k);
}
} else {
k--;
}
}
}
int main() {
read();
backtracking();
//permute(0);
write();
return 0;
}