Cod sursa(job #1002982)

Utilizator NaniteNanite Nanite Data 29 septembrie 2013 14:53:43
Problema ADN Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
#include <fstream>
#include <vector>

using namespace std;

bool equals(string a, string b) {
    if(a.length() != b.length()) {
            return false;
    } else {
        for(int i = 0; i < a.length(); i++) {
            if(a[i] != b[i]) {
                return false;
            }
        }
    }
    return true;
}

bool contains(string str, string in) {
    if(str.length() > in.length()) {
        return false;
    } else {
        for(int i = 0; i < in.length() - str.length(); i++) {
            if(equals(str, in.substr(i, str.length()))) {
                return true;
            }
        }
    }

    return false;
}

bool endsWith(string str, string in) {
    if(str.length() > in.length()) {
        return false;
    } else {
        return equals(str, in.substr(in.length()-str.length(), str.length()));
    }
}

int main() {
    const char fileIn[] = "adn.in",
                fileOut[] = "adn.out";

    fstream file(fileIn, ios::in);

    vector<string> l;
    vector<string>::iterator it;
    string strBuffer;
    int n;

    file >> n;
    for(int i = 0; i < n; i++) {
        file >> strBuffer;
        l.push_back(strBuffer);
    }

    file.close();

    int intBuffer;
    int index = -1, length;

    while(l.size() > 1) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(i != j) {
                    if(contains(l.at(j), l.at(i))) {
                        l.erase(l.begin() + j);

                        if(j < i) {
                            i--;
                        }
                        n--;
                        j--;
                        continue;
                    }

                    if(l.at(i).length() < l.at(j).length()) {
                        intBuffer = l.at(i).length();
                    } else {
                        intBuffer = l.at(j).length();
                    }

                    for(int k = intBuffer-1; k > 0; k--) {
                        if(endsWith(l.at(i).substr(0, k), l.at(j))) {
                            if(index == -1 || k > length) {
                                index = j; length = k;
                                break;
                            }
                        }
                    }
                }
            }

            if(index != -1) {
                it = l.begin() + i;
                (*it) = l.at(index) + l.at(i).substr(length, l.at(i).length() - length);

                it = l.begin() + index;

                l.erase(it);
                if(index < i) {
                    i--;
                }
                n--;

                index = -1;
            }
        }
    }

    file.open(fileOut, ios::out);
    file << l.at(0);

    return 0;
}