Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Deorowicz S.

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: constrained longest common subsequence

Sortuj według:

Ogranicz wyniki do:

Bit-Parallel Algorithm for the Constrained Longest Common Subsequence Problem

Deorowicz S.

Fundamenta Informaticae

2010

Vol. 99, nr 4

409-433

The problem of finding a constrained longest common subsequence (CLCS) for the sequences A and B with respect to the sequence P was introduced recently. Its goal is to find a longest subsequence C of A and B such that P is a subsequence of C. Most of the algorithms solving the CLCS problem are based on dynamic programming. Bit-parallelism is a technique of using single bits in a machine word for concurrent computation. We propose the first bit-parallel algorithm computing a CLCS and/or its length which outperforms the other known algorithms in terms of speed.

Fast algorithm for the constrained longest common subsequence problem

Deorowicz S.

Theoretical and Applied Informatics

2007

Vol. 19, No. 2

91-102

The problem of finding the constrained longest common subsequence (CLCS) for the sequences A and B with respect to the sequence P was introduced recently. Its goal is to find the longest subsequence of A and B such that P is a subsequence of it. The best known algorithms for its solving require time of order of a product of the sequence lengths. We introduce a novel approach in which time and space complexities depend also on the number of matches between A, B, and P. The time complexity is better for typical parameter settings and never worse.

Problem wyznaczania najdłuższego wspólnego podciągu ciągów A i B, którego podciągiem jest podciąg P (CLCS) pojawił się˛ literaturze stosunkowo niedawno. Złożoności obliczeniowe najlepszych znanych algorytmów są˛ iloczynem długości wszystkich ciągów. W niniejszej pracy przedstawione jest nowy algorytm rozwiązywania tego problemu, dla którego złożoność´ obliczeniowa zależy od liczby dopasować pomiędzy ciągami A, B i P. Złożoność´ ta jest zwykle lepsza (a nigdy gorsza) niż najlepszych znanych do tej pory algorytmów.