Cod sursa(job #1002991)

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

using namespace std;

bool equals(string a, string b) {
    if(a.compare(b) == 0) {
        return true;
    }

    return false;
}

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) {
        return equals(str, in.substr(in.length()-str.length(), str.length()));
}

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

    ifstream fileInStream(fileIn);
    ofstream fileOutStream(fileOut);

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

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

    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;
            }
        }
    }

    fileOutStream << l.at(0);



    return 0;
}