Cod sursa(job #1002924)

Utilizator NaniteNanite Nanite Data 29 septembrie 2013 11:22:46
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.81 kb
#include <iostream>
#include <fstream>
#include <limits>
#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();

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n;) {
            if(i != j) {
                if(contains(l.at(j), l.at(i))) {
                    l.erase(l.begin() + j);
                    if(j < i) {
                        i--;
                    }
                    n--;
                } else {
                    j++;
                }
            } else {
                j++;
            }
        }
    }

    int intBuffer;
    int index = -1, length;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(i != j) {
                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;
}