Cod sursa(job #1006341)

Utilizator NaniteNanite Nanite Data 6 octombrie 2013 21:24:22
Problema ADN Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.18 kb
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

const unsigned int maxl = 30000,
                    maxn = 18;
unsigned int N;
string s[maxn];
unsigned short kmpTable[maxn][maxl],
                used[maxn];

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

void createKmpTable(string a, unsigned short *table) {
    unsigned int x = 0, it = 0;
    table[0] = 0;
    for(int i = 1; i < a.length(); ++i) {
        if(a[i] == a[it]) {
            ++x;
            table[i] = x;
            ++it;
        } else {
            it = 0;
            x = 0;
            if(a[i] == a[it]) {
                ++x;
                table[i] = x;
                ++it;
            } else {
                table[i] = x;
                ++it;
            }
        }
    }
}

int kmpSearch(string pattern, string in, unsigned short *kmpTable) {
    unsigned int index = 0, match = 0;

    while(index + match < in.length()) {
        if(pattern[match] == in[index + match]) {
            ++match;
            if(match >= pattern.length()) {
                return index;
            }
        } else {
            if(match > 0) --match;
            index = index + 1 + match - kmpTable[match];
            match = 0;
        }
    }

    return -1;
}


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

inline void write() {
    for(int i = 0; i < N; ++i) {
        if(used[i] == 0) {
            fileOutStream << s[i];
        }
    }
}

bool equals(string s1, unsigned int pos1, string s2, unsigned int pos2, unsigned int length) {
    unsigned int i = pos1, j = pos2;
    while(i - pos1 < length) {
        if(s1[i] != s2[j]) {
            return false;
        }
        ++i; ++j;
    }

    return true;
}

bool finished() {
    int n = 0;
    for(int i = 0; i < N; ++i) {
        if(used[i] != 1) {
            ++n;
        }
    }

    if(n > 1) {
        return false;
    }

    return true;
}

inline void solve() {
    int j, k, x,
        index = -1, l;

while(!finished()) {
    for(int i = 0; i < N; ++i) {if(used[i] == 1) continue;
        for(j = 0; j < N; ++j) {
            if(i != j && used[j] != 1) {
                if(s[i].length() >= s[j].length() && kmpSearch(s[j], s[i], kmpTable[j]) != -1) {
                    used[j] = 1;
                }
            }
        }

        for(j = 0; j < N; ++j) {if(i == j || used[j]) continue;
            s[i] > s[j] ? k = s[j].length() : k = s[i].length()-1;
            for(; k > 0; --k) {
                if(equals(s[i], s[i].length()-k, s[j], 0, k)) {
                    if(index == -1 || k > l) {
                        l = k;
                        index = j;
                    }
                }
            }
        }

        if(index != -1) {
            s[i] += s[index].substr(l, s[index].length() - l);
            used[index] = 1;
            index = -1;
        }
    }
}
}

int main() {
    int i;

    read();
    solve();
    write();



    return 0;
}