Witam,
próbuje wykonać zadanie http://pl.spoj.com/problems/LENLCS/ ale coś mi nie chce wyjść, testy wykonuje poprawnie, ale na spoj daje mi SIGABRT. Korzystam z algorytmu z tej strony https://www.ics.uci.edu/~eppstein/161/960229.html który to jest ostatni (Space-efficient LCS - Reduced Space complexity) ponieważ chciałem mieć jak największą wydajność, a mój poprzedni przekraczał limit czasu. Moje pytanie brzmi, jak ten program poprawić i udoskonalić bo już sam nie wiem. Aktualnie valgrind nie pokazuje żadnych errorów i memory leak'ów.
Algorytm z tej strony wygląda następująco, w oryginalnej formie:
Space-efficient LCS:
int LCS(char * A, char * B)
{
allocate storage for one-dimensional arrays X and Y
for (i = m; i >= 0; i--)
{
for (j = n; j >= 0; j--)
{
if (A[i] == '\0' || B[j] == '\0') X[j] = 0;
else if (A[i] == B[j]) X[j] = 1 + Y[j+1];
else X[j] = max(Y[j], X[j+1]);
}
Y = X;
}
return X[0];
}
Wykonałem małe modyfikacje, ponieważ używam operatora new i zostałem zmuszony użycia zmiennej bool'owskiej aby usunąć wskaźnik Y w pierwszym obiegu pętli unikając memory leak'a.
W obecnej formie, mój program wygląda następująco, prosiłbym o jakieś wskazówki co do niego.
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring> // strlen
#include <algorithm> // max
using namespace std;
int LCS(const char * A, const char * B, int m, int n) {
int i, j;
bool toDestroy = false; // do ubicia Y
// alokacje pamieci
int * X = 0;
int * Y = 0;
if(X == 0 && Y == 0) {
X = new int[m+1];
Y = new int[n+1];
}
// algorytm
for (i = m; i >= 0; i--) {
for (j = n; j >= 0; j--) {
if (A[i] == '\0' || B[j] == '\0') X[j] = 0;
else if (A[i] == B[j]) X[j] = 1 + Y[j+1];
else X[j] = max(Y[j], X[j+1]);
}
if(!toDestroy) { // do ubicia tego na co wskazuje Y w pierwszym obiegu petli, dzieki temu nie mam memory leak
delete [] Y;
toDestroy = true;
}
Y = X;
}
int result = X[0];
if(X != 0 && Y != 0) { // sprzatanie
delete [] X;
}
X = 0;
Y = 0;
return result; // zwroc wynik
}
int main() {
std::ios_base::sync_with_stdio(0);
int t, n;
int a, b;
string s1, s2;
cin >> t;
for(int i = 0; i < t; ++i) {
cin >> a >> ws; // dlugosc s1
getline(cin, s1); // pierwszy wyraz
cin >> b >> ws; // dlugosc s2
getline(cin, s2); // drugi wyraz
cout << LCS(s1.c_str(), s2.c_str(), a, b) << endl; // uruchomienie algorytmu
}
return 0;
}
Z góry dzięki za pomoc :)