Skip to Content

Instrukcja korzystania z Biblioteki

Serwisy:

Ukryty Internet | Wyszukiwarki specjalistyczne tekstów i źródeł naukowych | Translatory online | Encyklopedie i słowniki online

Translator:

Kosmos
Astronomia Astrofizyka
Inne

Kultura
Sztuka dawna i współczesna, muzea i kolekcje

Metoda
Metodologia nauk, Matematyka, Filozofia, Miary i wagi, Pomiary

Materia
Substancje, reakcje, energia
Fizyka, chemia i inżynieria materiałowa

Człowiek
Antropologia kulturowa Socjologia Psychologia Zdrowie i medycyna

Wizje
Przewidywania Kosmologia Religie Ideologia Polityka

Ziemia
Geologia, geofizyka, geochemia, środowisko przyrodnicze

Życie
Biologia, biologia molekularna i genetyka

Cyberprzestrzeń
Technologia cyberprzestrzeni, cyberkultura, media i komunikacja

Działalność
Wiadomości | Gospodarka, biznes, zarządzanie, ekonomia

Technologie
Budownictwo, energetyka, transport, wytwarzanie, technologie informacyjne

Effective Sparse Dynamic Programming Algorithms for Merged and Block Merged LCS Problems

The longest common subsequence problem has been widely studied and used to find out the relationship between sequences. In this paper, we study the interleaving relationship between sequences, that is, we measure the relationship among three sequences, where two of those are interleaved in different ways and then the interleaved sequences are subsequently matched with the third remaining sequence, as pairwise longest common subsequence problems. Given a target sequence T and two other sequences A and B, we need to find out the LCS between M(A,B) and T, where M(A,B) denotes the mergedsequence which consists of A and B. We first present an improved O((Rr + Pm) log log r) time algorithm, where we consider only the matches between sequences; here |T| = n, |A| = m and |B| = r (m _ r); R is the total number of ordered pairs of positions at which the two strings A and T match and P denotes the total number of ordered pairs of positions at which the two strings B and T match. Basing on the same idea, we also propose an improved algorithm to solve a block constrained variation of the problem. Running time of the blocked version is O(max{R_ log log r,P_ log log r}), where _ denotes the number of blocks in A and _ denotes the number of blocks in B. However, these improved algorithms do not provide best output in every cases. Therefore we finally fabricate a hybrid algorithm which utilizes the advantages of our proposed algorithms and previous state of the arts algorithms to provide best output in every possible cases, from both time efficiency and space efficiency.

Journal of Computers 2014/07/26 - 18:24 Czytaj