Cod sursa(job #1008669)

Utilizator NaniteNanite Nanite Data 11 octombrie 2013 16:17:29
Problema ADN Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <fstream>

using namespace std;

const unsigned int maxl = 30000,
                    maxn = 18;
unsigned int N,
             kmpTable[maxn][maxl];
string s[maxn],
        stringBuffer,
        S = "";

ifstream fileInStream("adn.in");
ofstream fileOutStream("adn.out");


inline void read() {
    fileInStream >> N;
    for(int i = 0; i < N; i++) {
        fileInStream >> s[i];
    }
}

inline void write() {
    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[stringIndex][pos2++]) {
            return false;
        }
    }

    return true;
}

string compress() {
    unsigned int x;
    string buffer = "";
    for(unsigned int i = 0; i < N; ++i) {
        for(buffer.length() < s[i].length() ? x = buffer.length() : x = s[i].length(); x >= 0; --x) {
            if(equals(buffer, buffer.length()-x, i, 0, x)) {
                buffer += s[i].substr(x, s[i].length()-x);
                break;
            }
        }
    }

    return buffer;
}

void permute(unsigned int it) {
    if(it == N) {
        stringBuffer = compress();
        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]);
        }
    }
}


int main() {
    read();
    permute(0);
    write();



    return 0;
}