[Algorytm LCS] Dla wielu ciągów

0

Witajcie, przeszukałem forum ale niestety nie natrafiłem na żaden ślad który pomógłby mi w rozwiązaniu problemu. Otóż piszę aplikację która ma implementować algorytm wyszukiwania najdłuższego podciągu ALE dla wielu ciągów. Dla dwóch znam, bo linków w google jest aż za dużo. Natomiast nigdzie nie mogłem znaleźć dla 3 i więcej ciągów jak również nie mam żadnego pomysłu.

0

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#LCS_function_defined

Tu jest wzór na LCS. Gdy zastosujesz spamiętywanie, to ten kod można zapisać w C++ czy podobnym niemal bezpośrednio (dochodzi tylko case: jeśli wartość już obliczona to ją zwróć).

Dorobienie trzeciej zmiennej, Zj jest raczej trywialne:

  • warunek w drugiej linii zmieniamy na: if xi = yj = zk
  • akcję w drugiej linii zamieniamy na: (LCS(Xi-1, Yj-1, Zk-1) + x)
  • warunek w ostatniej linii zamieniamy po prostu na else - w zasadzie ten warunek zachowuje się dokładnie tak jak else,
  • akcję w trzeciej linii zamieniamy na: longest(LCS(Xi-1, Yj-1, Zk), LCS(Xi-1, Yj, Zk-1), LCS(Xi, Yj-1, Zk-1))

Po wykonaniu algorytmu dostaniesz LCS w komórce Xm, Yn, Zo.

Zamiana tego na postać dynamiczną jest trywialna jeśli ma się kod dla wersji dwuwymiarowej.

Dla n stringów algorytm wymaga tablicy n wymiarowej!!!

Np dla piętnastu stringów stuznakowych wymaga 100 ^ 15 komórek :)

0

Rozumiem mniej więcej co napisałeś, tylko sęk w tym, że ja potrzebuję taki algorytm który będzie mógł obsłużyć dowolną ilość ciągów wejściowych (przykladowo 5 czy 7) a nie że ja na "sztywno" napiszę funkcję.

0

No to zamiast tablicy wielowymiarowej możesz:

  • zrobić tablicę stałowymiarową (np jednowymiarową) i bawić się z indeksami,
  • zrobić haszmapę list (czy tam wektorów) mapującą listę współrzędnych na zawartość elementu - cholernie wolne ale eleganckie,

Dla przyspieszenia możesz wygenerować sztywny kod dla małych n.

Ewentualnie może da się to obejść za pomocą metaprogramowania, ale to już zależy od języka.

0

W zadaniu mam wykorzystać programowanie dynamiczne. Ten algorytm na wiki by się nadawał właśnie tylko że jest on dla 2 ciągów.

0

No to zostaje zabawa ze wskaźnikami / indeksami.

Np zamiast:

int a[5][10][15];
a[3][4][7] = 8;

zrobić:

int a[5 * 10 * 15];
a[(3*10 + 4)*15 + 7] = 8;

Można to nawet mocno przyspieszyć. Odległość pomiędzy &LCS[x, y, z] i &LCS[x - 1, y, z] jest stała, podobnie dla reszty przypadków. Można więc sobie te odległości stablicować. Kod wyjdzie równie elegancki co w przypadku szczególnym (tzn ustalony wymiar) :)

0
/* 
 * File:   main.cpp
 * Author: Piotrek
 *
 * Created on 27 sierpień 2010, 17:52
 */

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<string> A;
vector<int> L;
int *LCS;
int cellsNum;
int *distances;
int sumDistances;
int N;

bool hasZero(int *indexes) {
    bool result = false;
    for (int i = 0; (!result) && (i < N); i++) {
        result |= indexes[i] == 0;
    }
    return result;
}

bool equal(int *indexes) {
    bool result = true;
    for (int i = 1; result && (i < N); i++) {
        result &= A[i - 1][indexes[i - 1]] == A[i][indexes[i]];
    }
    return result;
}

int longest(int index) {
    int result = 0;
    for (int i = 0; i < N; i++) {
        if (LCS[index - distances[i]] > result) {
            result = LCS[index - distances[i]];
        }
    }
    return result;
}

void nextIndex(int *indexes) {
    for (int i = N - 1; i >= 0; i--) {
        indexes[i]++;
        if (indexes[i] == L[i]) {
            indexes[i] = 0;
        } else {
            break;
        }
    }
}

void computeLCS() {
    int *indexes = new int[N];
    for (int i = 0; i < N; i++) {
        indexes[i] = 0;
    }
    for (int i = 0; i < cellsNum; i++) {
        if (LCS[i] == - 1) {
            if (hasZero(indexes)) {
                LCS[i] = 0;
            } else if (equal(indexes)) {
                LCS[i] = LCS[i - sumDistances] + 1;
            } else {
                LCS[i] = longest(i);
            }
        }
        nextIndex(indexes);
    }
}

int main(int argc, char** argv) {


    cin >> N;
    distances = new int[N];
    cellsNum = 1;
    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        s = " " + s;
        A.push_back(s);
        L.push_back(s.size());
        cellsNum *= s.size();
    }

    int distance = 1;
    sumDistances = 0;
    for (int i = N - 1; i >= 0; i--) {
        distances[i] = distance;
        sumDistances += distance;
        distance *= L[i];
    }

    LCS = new int[cellsNum];

    for (int i = 0; i < cellsNum; i++) {
        LCS[i] = -1;
    }

    computeLCS();

    printf("%d", LCS[cellsNum - 1]);

    return 0;
}

Noo wykodziłem dzisiaj to :P
Na wejściu jest liczba napisów, a potem tyle napisów. Na wyjściu jest dlugość LCS. Jak wrócę do domu to zrobię wypisywanie LCSów :)

0

No w końcu mi się zachciało i jest pełny algorytm (finezyjny może i nie jest, ale spełnia swoje zadanie):


/*
 * File:   main.cpp
 * Author: Piotrek
 *
 * Created on 27 sierpień 2010, 17:52
 *
 * Algorithm for computing LCS.
 *
 * Input:
 * - number of input strings,
 * - input strings in separate lines,
 *
 * Output:
 * - length of LCS,
 * - one of possible LCSes,
 */

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

// input strings with attached " " (which do not count for LCS but simplify things)
vector<string> A;
// lengths of input strings with attached " "
vector<int> L;
// emulating multi-dimensional array with one-dimenstional
int *LCS;
// total size of above array
int cellsNum;
// distance[i] tells how much we should move in emulated array if we want to increment/ decrement index in dimension i
int *distances;
// sum of above array - tells how much we should move if we want to increment/ decrement all indexes at once
int sumDistances;
// number of input strings
int N;
// length of LCS
int lcsLength;
// one of possibles LCSes
char* lcsString;

bool hasZero(int *indexes) {
    bool result = false;
    for (int i = 0; (!result) && (i < N); i++) {
        result |= indexes[i] == 0;
    }
    return result;
}

bool equal(int *indexes) {
    bool result = true;
    for (int i = 1; result && (i < N); i++) {
        result &= A[i - 1][indexes[i - 1]] == A[i][indexes[i]];
    }
    return result;
}

int longest(int index) {
    int result = 0;
    for (int i = 0; i < N; i++) {
        if (LCS[index - distances[i]] > result) {
            result = LCS[index - distances[i]];
        }
    }
    return result;
}

int computeLongestIndex(int index) {
    int result = 0;
    int longest = 0;
    for (int i = 0; i < N; i++) {
        if (LCS[index - distances[i]] > longest) {
            longest = LCS[index - distances[i]];
            result = i;
        }
    }
    return result;
}

void nextIndex(int *indexes) {
    for (int i = N - 1; i >= 0; i--) {
        indexes[i]++;
        if (indexes[i] == L[i]) {
            indexes[i] = 0;
        } else {
            break;
        }
    }
}

void computeLCS() {
    int *indexes = new int[N];
    for (int i = 0; i < N; i++) {
        indexes[i] = 0;
    }
    for (int i = 0; i < cellsNum; i++) {
        if (LCS[i] == - 1) {
            if (hasZero(indexes)) {
                LCS[i] = 0;
            } else if (equal(indexes)) {
                LCS[i] = LCS[i - sumDistances] + 1;
            } else {
                LCS[i] = longest(i);
            }
        }
        nextIndex(indexes);
    }
}

void traceLCS() {
    int *indexes = new int[N];
    int index = cellsNum - 1;
    for (int i = 0; i < N; i++) {
        indexes[i] = L[i] - 1;
    }
    for (int charsLeft = lcsLength; charsLeft > 0; charsLeft--) {
        while (!equal(indexes)) {
            int longestIndex = computeLongestIndex(index);
            indexes[longestIndex]--;
            index -= distances[longestIndex];
        }
        lcsString[charsLeft - 1] = A[0][indexes[0]];
        for (int i = 0; i < N; i++) {
            indexes[i]--;
        }
        index -= sumDistances;
    }
}

int main(int argc, char** argv) {

    cin >> N;
    cin.ignore();
    distances = new int[N];
    cellsNum = 1;
    for (int i = 0; i < N; i++) {
        string s;
        getline(cin, s);
        s = " " + s;
        A.push_back(s);
        L.push_back(s.size());
        cellsNum *= s.size();
    }

    int distance = 1;
    sumDistances = 0;
    for (int i = N - 1; i >= 0; i--) {
        distances[i] = distance;
        sumDistances += distance;
        distance *= L[i];
    }

    LCS = new int[cellsNum];

    for (int i = 0; i < cellsNum; i++) {
        LCS[i] = -1;
    }

    computeLCS();

    lcsLength = LCS[cellsNum - 1];
    lcsString = new char[lcsLength + 1];
    lcsString[lcsLength] = 0;

    cout << lcsLength << endl;

    traceLCS();

    cout << lcsString << endl;

    return 0;
}

Poprzedni post można skasować.

0

Wielkie dzięki. Przeanalizuję sobie kod aby go zrozumieć :D

EDIT: Czy Twoje rozwiązanie będzie złożoność obliczeniową O(k1k2...*km) ?
k1.. k2 - to długości poszczególnych ciągów
m - ilość ciągów wejściowych.

0

Nie. Złożoność jest taka jak na wiki:
user image

0

Przeanalizowałem sobie trochę twój kod i nasuwa mi się jedna myśl. Mianowicie będzie on miał ogromne zużycie pamięci, przykładowo dla 5 ciągów o przypadkowych długościach :

3, 5, 6, 9, 3

Rozmiar tablicy LCS wyniesie :

3 x 5 x 6 x 9 x 3 = 2430 bajtów

A to tylko dla 5 ciągów, w zadaniu mam napisane że algorytm ma działać z maksymalną liczbą 1000 ciągów. Wtedy pewnie ilość będzie już liczona w GB :D Tak więc poszperałem trochę w internecie, znalazłem stronkę ze zoptymalizowanym algorytmem http://edu.i-lo.tarnow.pl/inf/alg/001_search/0055.php w niższej części strony jest podana zoptymalizowana wersja która wymaga zdecydowanie mniejszej ilości pamięci. Co o tym sądzisz ?

0

Dobrze policzyłeś ten rozmiar.

Trik ze zmniejszeniem pamięci jest banalny i wiedziałem o nim. Pozwala on zbić złożoność pamięciową o jeden wymiar (przynajmniej według mojego rozumowania). Dla twoich długości stringów czyli 3, 5, 6, 9, 3 możemy wybrać najdłuższy string czyli ten o długości 9 i zbić jego wymiar, wtedy rozmiar tablicy LCS wyniesie:
2430 / 9 = 270 komórek (nie bajtów, jedna komórka ma 4 bajty bo są intami)

Dla 1000 ciągów o długości np 10 rozmiar pamięci to 101000 komórek czyli sporo więcej niż jest atomów we Wszechświecie, których jest 1080.

Możesz zastosować jakieś heurystyki do zbijania pamięci np usunąć te znaki z ciągów wejściowych, które nie pojawiają się we wszystkich ciągach. Inna heurystyka to taka, że jak np jakiś znak pojawia się w jednym stringu na początku i tylko raz, a w innym stringu tylko raz i to na końcu to spokojnie możesz wyrzucić ten znak ze wszystkich stringów (bo wspólny podciąg z tym znakiem ma długość co najwyżej 1). Tyle że to dość słabe heurezy.

W moim kodzie akurat bardzo łatwo dodać tą optymalizację ze zbijaniem jednego wymiaru. Wystarczy:

  1. Przenieść najdłuższy ciąg wejściowy na pierwszą pozycję,
  2. Zaalokować tylko [sumDistances] komórek, a nie [cellsNum] komórek, a potem zamiast indeksu [i] wyliczyć: [i < 0 ? i + sumDistances : i],

Oczywiście minus jest taki, że nie będzie się dało odtworzyć żadnego LCSa (tzn traceLCS się sypnie), a tylko obliczyć jego długość (co jest zresztą nieodłączną wadą tejże optymalizacji).

0

Mógłbyś pokazać jak to wygląda w kodzie ? Bo nie bardzo potrafię sobie to wyobrazić.

0

No to masz kiepską wyobraźnię :) . Ten kod powinien działać poprawnie:

/* 
 * File:   main.cpp
 * Author: Piotrek
 *
 * Created on 27 sierpień 2010, 17:52
 */

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<string> A;
vector<int> L;
int *LCS;
int cellsNum;
int *distances;
int sumDistances;
int N;

bool hasZero(int *indexes) {
    bool result = false;
    for (int i = 0; (!result) && (i < N); i++) {
        result |= indexes[i] == 0;
    }
    return result;
}

bool equal(int *indexes) {
    bool result = true;
    for (int i = 1; result && (i < N); i++) {
        result &= A[i - 1][indexes[i - 1]] == A[i][indexes[i]];
    }
    return result;
}

int longest(int index) {
    int result = 0;
    for (int i = 0; i < N; i++) {
        int anotherIndex = index - distances[i];
        anotherIndex = anotherIndex < 0 ? anotherIndex + sumDistances : anotherIndex;
        if (LCS[anotherIndex] > result) {
            result = LCS[anotherIndex];
        }
    }
    return result;
}

void nextIndex(int *indexes) {
    for (int i = N - 1; i >= 0; i--) {
        indexes[i]++;
        if (indexes[i] == L[i]) {
            indexes[i] = 0;
        } else {
            break;
        }
    }
}

void computeLCS() {
    int *indexes = new int[N];
    for (int i = 0; i < N; i++) {
        indexes[i] = 0;
    }
    for (int i = 0, index = 0; i < cellsNum; i++, index = index < sumDistances - 1 ? index + 1 : 0) {
        if (hasZero(indexes)) {
            LCS[index] = 0;
        } else if (equal(indexes)) {
            LCS[index]++;
        } else {
            LCS[index] = longest(index);
        }
        nextIndex(indexes);
    }
}

int main(int argc, char** argv) {


    cin >> N;
    distances = new int[N];
    cellsNum = 1;
    int maxSize = 0;
    int maxString = 0;
    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        s = " " + s;
        A.push_back(s);
        L.push_back(s.size());
        cellsNum *= s.size();
        if (s.size() > maxSize) {
            maxSize = s.size();
            maxString = i;
        }
    }
    string swapString = A[0];
    int swapIndex = L[0];
    A[0] = A[maxString];
    L[0] = L[maxString];
    A[maxString] = swapString;
    L[maxString] = swapIndex;

    int distance = 1;
    sumDistances = 0;
    for (int i = N - 1; i >= 0; i--) {
        distances[i] = distance;
        sumDistances += distance;
        distance *= L[i];
    }

    LCS = new int[sumDistances];

    computeLCS();

    printf("%d", LCS[(cellsNum - 1) % sumDistances]);

    return 0;
}
0

Hmm nie do końca rozumiem to co napisałeś (a przecież nie chodzi tylko o głupie skopiowanie kodu).

1.Dlaczego :

LCS[(cellsNum - 1) % sumDistances]);

Skąd to się wzięło ?

2.W jaki sposób mogę wziąć długość obliczonego LCS ? Poprzednio mogłem policzyć na podstawie lcs_string, ale w tym algorytmie nie jest budowany string (jest to jego cecha tak wyczytałem). poza tym po wklejeniu Twego kodu w Code::Blocks i podstawieniu dwóch ciągów :

2 3 4 5 6 7 8 9
2 4 3 6 11 9

dostaję wynik 9, a przecież poprawna odpowiedź najdłuższy wspólny podciąg ma długość 4.
Sorry że tak cię męczę, po prostu chce to zrozumieć ;)

0

LCS tych dwóch ciągów ma długość 9. Składa się z np:
2, spacja, 4, spacja, spacja, 6, spacja, spacja, 9
Program nie parsuje ciągów wejściowych, traktuje je jako po prostu ciągi znaków. Jak chcesz wczytywać inty to zrób parsowanie i zmień typ string na vector<int>.

To "% sumDistances" wzięło się z tego, że (jak już napisałem wcześniej) w tablicy pamiętam tylko [sumDistances] ostatnio obliczonych wartości, tzn w ostatniej wersji LCS jest kolejką cykliczną (buforem cyklicznym).

Załóżmy że mamy kolejkę o długości n i dodaliśmy do niej m elementów (nadpisując zawsze stare). Jeśli chcemy dobrać się do ostatniego elementu to jego indeks to (m - 1) % n.

Przez to że stare wartości są nadpisywane, tracimy informacje potrzebne do odtworzenia LCSa. Nie przeszkadza to jednak w obliczeniu długości LCSa.

Jeślibyś dokładnie poczytał o algorytmie to wiedziałbyś, że LCS[a][b][c][d] (itp) to długość LCS dla: a-znakowego prefixu pierwszego ciągu, b-znakowego prefixu drugiego ciągu, c-znakowego trzeciego ciągu i d-znakowego prefixu czwartego ciągu. Zresztą sama Wikipedia mówi:

Wikipedia napisał(a)

wartość C[i][j] jest długością NWP podciągów A[1..i] i B[1..j]

Nie czytasz nawet Wikipedii i zadajesz niepotrzebne pytania.

Sporo rzeczy wytłumaczyłem po angielsku w komentarzach. Np:

  • Input:
    • number of input strings,
    • input strings in separate lines,
  • Output:
    • length of LCS,
    • one of possible LCSes,

Widać całą specyfikację wejścia i wyjścia (dla wersji bez zbijania wymiaru). Jeśli nie rozumiesz angielskiego to napisz.

0

Ok już rozumiem. z algorytmów jestem noga. Napisałem sobie prostą funkcję do usuwania spacji z ciągu wejściowego:

void RemoveSpaces(string& text)
{
    string out;
    for(unsigned int i = 0; i < text.length(); ++i)
    {
         if(text[i] == ' ') continue;
        else out += text[i];
    }
    text = out;
}

Oczywiście tą spację na początku dodaję później. No i teraz działa tak jak chciałem.

0
def lcs[T](sequences: Iterable[Seq[T]]): Seq[T] = {
  
  def rest(s1: Seq[T], s2: Seq[T]): Option[Seq[T]] = s1 match {
    case Seq() => Some(s2)
    case Seq(x, xs @ _*) if (s2 contains x) => rest(xs, s2.dropWhile(_ != x).tail)
    case _ => None
  }
  
  def isSubsequence(s1: Seq[T], s2: Seq[T]) = rest(s1, s2).isDefined       
  def isValid(s: Seq[T]) = sequences.forall(isSubsequence(s, _))
    
  def isDominated(s1: Seq[T], s2: Seq[T]) = {
    val lenDiff = s2.length - s1.length    
    if (lenDiff == 0)
      sequences.forall(s => rest(s1, s).get.length <= rest(s2, s).get.length) &&
      (sequences.exists(s => rest(s1, s).get.length < rest(s2, s).get.length) || s1.hashCode < s2.hashCode)
    else if (lenDiff > 0)
      sequences.forall(s => rest(s1, s).get.length <= rest(s2, s).get.length + lenDiff)
    else
      false   
  }
  
  def prune(set: List[Seq[T]]) = 
    set.filterNot(s1 => set.exists(s2 => isDominated(s1, s2)))            
            
  def find(s: Seq[T], result: List[Seq[T]]): List[Seq[T]] = s match {
    case Seq() => result
    case Seq(x, xs @ _*) => 
      find(xs, prune(result ::: result.map(_ :+ x).filter(isValid)))
  }
  
  find(sequences.head, Seq() :: Nil).max(Ordering by {x: Seq[T] => x.length})
}

Dla 1000 sekwencji:


scala> lcs((Stream continually Seq(1,2,5,3,7,8) take 500 toList) ::: (Stream continually Seq(5,1,3,1,8,9) take 500 toList))
res54: Seq[Int] = List(1, 3, 8)

Czas poniżej sekundy, pamięć nie wiem, ale jakieś pojedyncze kilobajty chyba.
Programowanie dynamiczne rządzi. Wikipedię spalić. :D

0

Krolik:
Skąd wziąłeś ten algorytm? Jest gdzieś dowód jego złożoności?

Ciekawe jak by to wyglądało w Haskellu. Może deus się pokusi i pokaże? :)

0

Wymyśliłem. ;]

Dowodu złożoności nie ma. Trywialne ograniczenie górne: O(2^n), gdzie n = długość pierwszego ciągu.
Ale ponieważ tam jest silny pruning, to w praktyce działa duuużo lepiej. Na razie nie udało mi się wymyślić sensownego przypadku, który by pokazał tę "wykładniczość". Dla ciągów zupełnie losowych działa b. dobrze.

0

Kozak :P Pasuje przetestować to na robieniu diffów z jakiegoś CVSa.

Nie obrazisz się gdy podyskutuję o złożoności na jakimś forum albo z jakimś doktorkiem? :)

0

Nie. Bardzo chętnie jakby ktoś to w ogóle sprawdził :)
No, i bardzo chętnie dowiem się, czy istnieje jakieś lepsze ograniczenie na złożoność, np. może da się udowodnić coś ładnego dla jakiejś klasy problemów (np. średnią złożoność). Wydaje mi się też, że dla dokładnie dwóch ciągów ten algorytm będzie gorszy niż ten z wikipedii (właściwie to wymyślałem go bardziej z myślą o dużej liczbie krótkich ciągów niż małej liczbie długich).

// Dopisane: teraz widzę, że można to jeszcze bardziej przyspieszyć, bo np. wywołania f-cji rest spokojnie można buforować i bardzo dużo zaoszczędzić. Do tego pruning też mógłby być lepszy. Jak znajdę chwilę, to wrzucę poprawioną wersję.

// Dopisane później:
Poprawiona wersja algorytmu:

def lcs[T](sequences: Iterable[Seq[T]]): Seq[T] = {
  
  case class SubSeq(data: Seq[T]) {
    val endVector = sequences map (s => rest(data, s) map (s.length - _.length))
    val isValid = endVector.forall(_.isDefined)
    val length = data.length
    def :+ (item: T) = SubSeq(data :+ item)   
  }
  
  def rest(s1: Seq[T], s2: Seq[T]): Option[Seq[T]] = s1 match {
    case Seq() => Some(s2)
    case Seq(x, xs @ _*) if (s2 contains x) => rest(xs, s2.dropWhile(_ != x).tail)
    case _ => None
  }
      
  def isDominated(s1: SubSeq, s2: SubSeq) = {
    val lenDiff = s2.length - s1.length    
    (lenDiff >= 0) && (s1.endVector zip s2.endVector).forall(x => x._1.get >= x._2.get + lenDiff)
  }
  
  def prune(set: List[SubSeq]) = {    
    def pruneRecursive(input: List[SubSeq], output: List[SubSeq]): List[SubSeq] = input match {
      case Nil => 
        output
      case x :: xs if output.exists(isDominated(x, _)) || xs.exists(isDominated(x, _)) => 
        pruneRecursive(xs, output)
      case x :: xs =>
        pruneRecursive(xs, x :: output)
    }
    pruneRecursive(set, Nil)    
  }    
  
            
  def find(s: SubSeq, result: List[SubSeq]): List[SubSeq] = s match {
    case SubSeq(Seq()) => result
    case SubSeq(Seq(x, xs @ _*)) => 
      find(SubSeq(xs), prune(result ::: result.map(_ :+ x).filter(_.isValid)))
  }
  
  find(SubSeq(sequences.head), SubSeq(Seq()) :: Nil).max(Ordering by {x: SubSeq => x.length}).data
}

Dla 2 ciągów oszacowanie złożoności pesymistycznej O(n5). Znacznie gorzej niż dla tego z Wikipedii, ale... udaje mi się tym programem rozwiązać zadanie np. dla 70 ciągów po 70 elementów każdy, dla elementów z zakresu 0..9, w kilka sekund. Dla porównania algorytm z Wikipedii potrzebowałby na to 7070 operacji... :D Dla dwóch ciągów też nie jest wcale tak źle jakby sugerowało O(n^5) (albo przynajmniej jest b. mała stała) - ciągi długości 200 elementów daje się robić w rozsądnym czasie.

Podejrzewam, że gdyby pruning zrobić inteligentniej, a nie każdy z każdym, jak jest teraz, to ten algorytm by nieźle wymiatał. Gdyby np. pruning robić w O(n) zamiast O(n2), to pesymistyczna złożoność algorytmu dla 2 ciągów zredukowałaby się do O(n3).

1 użytkowników online, w tym zalogowanych: 0, gości: 1