algorytm.org

Najdłuższe wspólne podsłowo

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Najdłuższe wspólne podsłowo
Ocena użytkowników:***** / 7
SłabyŚwietny 
Wpisany przez Rafał Świetlicki, 18 stycznia 2007 12:04

Niech s = s1s2...sm, t = t1t2...tn (m, n ≥ 1) będą dowolnymi słowami nad dowolnym alfabetem. Zadaniem jest znalezienie możliwie najdłuższego słowa nad tym samym alfabetem, które stanowiłoby wzorzec jednocześnie w słowie s jak i t. Opisany poniżej algorytm wykorzystuje pojęcie sufiksu (znaczenie tego pojęcia jest wyjaśnione m.in. w artykule algorytm KMP (Knutha-Morrisa-Pratta)) oraz ideę programowania dynamicznego. Niech aij (1 ≤ i ≤ m, 1 ≤ j ≤ n) oznacza długość najdłuższego wspólnego sufiksu słów s’= s1s2...si oraz t’= t1t2...tj. Wówczas mamy dwie możliwości:
  • jeżeli si != tj, to aij = 0,
  • w przeciwnym razie aij = ai-1 j-1 + 1 (przyjmujemy dodatkowo ai0 = a0j = 0).

Na koniec wystarczy znaleźć największą wartość w tablicy dwuwymiarowej a. Zapamiętując jednocześnie, na której pozycji w tablicy a wystąpiła wartość największa, można podać również postać najdłuższego podsłowa słów s oraz t.

Realizacja powyższego algorytmu mogłaby wyglądać następująco:

długość najdłuższego wspólnego podsłowa = 0;
m = długość słowa s;
n = długość słowa t;
dla k = 0, 1, ..., (maksymalny rozmiar tablicy dwuwymiarowej a) – 1
  a[0][k] = a[k][0] = 0;
dla i = 1, 2, ..., m
  dla j = 1, 2, ..., n
      jeżeli si != tj to a[i][j] = 0;
      w przeciwnym razie
        a[i][j] = a[i-1][j-1] + 1;
        jeżeli a[i][j] > długość najdłuższego wspólnego podsłowa to
            długość najdłuższego wspólnego podsłowa = a[i][j];

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiAda
.ada
.ada
***** / 1
Rafał ŚwietlickiC/C++
.cpp
.cpp
***** / 6
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 1
Tomasz LubińskiJava
.java
.java
***** / 4
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 30 lipca 2012 18:32
Dodaj komentarz