Cod sursa(job #3284317)

Utilizator deyrownntdeyrownnt deyrownnt Data 11 martie 2025 14:11:13
Problema ADN Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.29 kb

#include <iostream>
#include <fstream>
#include <string>
#define MAX_SIZE 30001
#define MAX_SEC 18
using namespace std;

ifstream fin("adn.in");
ofstream fout("adn.out");

// Funcție pentru a verifica dacă s este subsecvență a t
bool isSubsequence(char s[], char t[]) {
    int i = 0, j = 0;
    while (s[i] != '\0' && t[j] != '\0') {
        if (s[i] == t[j]) {
            i++;
        }
        j++;
    }
    return s[i] == '\0';
}

// Funcție pentru a găsi suprapunerea maximă între sfârșitul lui a și începutul lui b
int findOverlap(char a[], char b[]) {
    int lenA = strlen(a);
    int lenB = strlen(b);
    int maxOverlap = 0;
    
    for (int i = 1; i <= lenA && i <= lenB; i++) {
        bool isMatch = true;
        for (int j = 0; j < i; j++) {
            if (a[lenA - i + j] != b[j]) {
                isMatch = false;
                break;
            }
        }
        if (isMatch) {
            maxOverlap = i;
        }
    }
    
    return maxOverlap;
}

// Funcție pentru a combina două secvențe cu suprapunere
void mergeWithOverlap(char result[], char a[], char b[], int overlap) {
    strcpy(result, a);
    strcat(result, b + overlap);
}

// Funcție pentru a copia un string
void stringCopy(char dest[], char src[]) {
    int i;
    for (i = 0; src[i] != '\0'; i++) {
        dest[i] = src[i];
    }
    dest[i] = '\0';
}

// Funcție pentru a citi datele de intrare
void citire(int& n, char secvente[MAX_SEC][MAX_SIZE]) {
    fin >> n;
    fin.ignore(); // ignoră newline după citirea lui n
    
    for (int i = 0; i < n; i++) {
        fin.getline(secvente[i], MAX_SIZE);
    }
}

int main() {
    int n;
    char secvente[MAX_SEC][MAX_SIZE];
    bool folosit[MAX_SEC] = {false};
    char rezultat[MAX_SIZE * MAX_SEC] = "";
    
    citire(n, secvente);
    
    // Alegem prima secvență ca punct de start
    stringCopy(rezultat, secvente[0]);
    folosit[0] = true;
    int nrFolosite = 1;
    
    // Cât timp nu am folosit toate secvențele
    while (nrFolosite < n) {
        int bestI = -1;
        int maxOverlap = -1;
        
        // Găsim secvența nefolosită cu cea mai mare suprapunere cu rezultatul curent
        for (int i = 0; i < n; i++) {
            if (!folosit[i]) {
                // Verificăm suprapunerea în ambele direcții
                int overlap1 = findOverlap(rezultat, secvente[i]);
                int overlap2 = findOverlap(secvente[i], rezultat);
                
                if (overlap1 > maxOverlap) {
                    maxOverlap = overlap1;
                    bestI = i;
                }
                
                // Dacă există o suprapunere mai bună în cealaltă direcție, 
                // vom adăuga secvența la început în loc de sfârșit
                if (overlap2 > maxOverlap) {
                    maxOverlap = overlap2;
                    bestI = -(i + 1); // Marcare negativă pentru a indica direcția
                }
            }
        }
        
        // Dacă am găsit o secvență cu suprapunere
        if (bestI >= 0) {
            // Verificăm dacă secvența este deja conținută în rezultat
            if (strstr(rezultat, secvente[bestI]) != NULL) {
                folosit[bestI] = true;
                nrFolosite++;
                continue;
            }
            
            // Adăugăm secvența la sfârșit cu suprapunere
            char newResult[MAX_SIZE * MAX_SEC];
            mergeWithOverlap(newResult, rezultat, secvente[bestI], maxOverlap);
            stringCopy(rezultat, newResult);
            folosit[bestI] = true;
        } 
        else if (bestI < 0) {
            int realI = -bestI - 1;
            
            // Verificăm dacă secvența este deja conținută în rezultat
            if (strstr(rezultat, secvente[realI]) != NULL) {
                folosit[realI] = true;
                nrFolosite++;
                continue;
            }
            
            // Adăugăm rezultatul la sfârșitul secvenței cu suprapunere
            char newResult[MAX_SIZE * MAX_SEC];
            mergeWithOverlap(newResult, secvente[realI], rezultat, maxOverlap);
            stringCopy(rezultat, newResult);
            folosit[realI] = true;
        }
        
        nrFolosite++;
    }
    
    fout << rezultat << endl;
    
    fin.close();
    fout.close();
    
    return 0;
}