Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
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 language | English |
---|---|
Title of host publication | 50th International Conference on Parallel Processing, ICPP 2021 - Main Conference Proceedings |
Publisher | Association for Computing Machinery |
Number of pages | 10 |
ISBN (Electronic) | 9781450390682 |
DOIs | |
State | Published - 9 Aug 2021 |
Event | 50th International Conference on Parallel Processing, ICPP 2021 - Virtual, Online, United States Duration: 9 Aug 2021 → 12 Aug 2021 |
Name | ACM International Conference Proceeding Series |
---|
Conference | 50th International Conference on Parallel Processing, ICPP 2021 |
---|---|
Country/Territory | United States |
City | Virtual, Online |
Period | 9/08/21 → 12/08/21 |
ID: 90974852