Wyniki wyszukiwania - BazTech

1

Computing a Longest Common Palindromic Subsequence

Chowdhury S. R., Hasan M. M., Iqbal S., Rahman M. S.

Fundamenta Informaticae

|

2014

|

Vol. 129, nr 4

329--340

EN

The longest common subsequence (LCS) problem is a classic and well-studied problem in computer science. Palindrome is a word which reads the same forward as it does backward. The longest common palindromic subsequence (LCPS) problem is a variant of the classic LCS problem which finds a longest common subsequence between two given strings such that the computed subsequence is also a palindrome. In this paper, we study the LCPS problem and give two novel algorithms to solve it. To the best of our knowledge, this is the first attempt to study and solve this problem.

2

Bit-Parallel Algorithm for the Constrained Longest Common Subsequence Problem

Deorowicz S.

Fundamenta Informaticae

|

2010

|

Vol. 99, nr 4

409-433

EN

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.

3

Fast algorithm for the constrained longest common subsequence problem

Deorowicz S.

Theoretical and Applied Informatics

|

2007

|

Vol. 19, No. 2

91-102

EN

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.

PL

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.

4

Speeding-up Hirschberg and Hunt-Szymanski LCS Algorithms

Crochemore M., Iliopoulos C.S., Pinzon Y.J.

Fundamenta Informaticae

|

2003

|

Vol. 56, nr 1,2

89-103

EN

Two algorithms are presented that solve the problem of recovering the longest common subsequence of two strings. The first algorithm is an improvement of Hirschberg's divide-and-conquer algorithm. The second algorithm is an improvement of Hunt-Szymanski algorithm based on an efficient computation of all dominant match points. These two algorithms use bit-vector operations and are shown to work very efficiently in practice.