Cod sursa(job #1008198)

Utilizator NaniteNanite Nanite Data 10 octombrie 2013 16:25:06
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <fstream>

using namespace std;

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

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 s1, unsigned int pos1, string s2, unsigned int pos2, unsigned int length) {
    unsigned int i = pos1;
    while(i - pos1 < length) {
        if(s1[i] != s2[pos2]) {
            return false;
        }
        ++i; ++pos2;
    }

    return true;
}

string compress() {
    unsigned int x;
    string buffer = "";
    for(unsigned int i = 0; i < N; ++i) {
        buffer.length() < s[i].length() ? x = buffer.length() : x = s[i].length();
        for(; x >= 0; --x) {
            if(equals(buffer, buffer.length()-x, s[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() {
    int i;

    read();
    permute(0);
    write();



    return 0;
}