Pagini recente » Cod sursa (job #3253836) | Cod sursa (job #2177284) | Cod sursa (job #3277925) | Cod sursa (job #803262) | Cod sursa (job #3284317)
#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;
}