The longest common subsequence (LCS) problem on a pair of strings is a classical problem in string algorithms. Its extension, the semi-local LCS problem, provides a more detailed comparison of the input strings, without any increase in asymptotic running time. Several semi-local LCS algorithms have been proposed previously; however, to the best of our knowledge, none have yet been implemented. In this paper, we explore a new hybrid approach to the semi-local LCS problem. We also propose a novel bit-parallel LCS algorithm. In the experimental part of the paper, we present an implementation of several existing and new parallel LCS algorithms and evaluate their performance.

Original languageEnglish
Title of host publication50th International Conference on Parallel Processing, ICPP 2021 - Main Conference Proceedings
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Electronic)9781450390682
DOIs
StatePublished - 9 Aug 2021
Event50th International Conference on Parallel Processing, ICPP 2021 - Virtual, Online, United States
Duration: 9 Aug 202112 Aug 2021

Publication series

NameACM International Conference Proceeding Series

Conference

Conference50th International Conference on Parallel Processing, ICPP 2021
Country/TerritoryUnited States
CityVirtual, Online
Period9/08/2112/08/21

    Research areas

  • bit-parallel algorithms, braid multiplication, divide-and-conquer, dynamic programming, longest common subsequence, parallel algorithms, parallel braid multiplication, semi-local string comparison, string algorithms

    Scopus subject areas

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications

ID: 90974852