Space-efficient approximate string matching allowing inversions in fast average time

Hwee Kim, Yo Sub Han

Research output: Chapter in Book/Report/Conference proceedingConference contribution


An inversion is one of the important operations in bio sequence analysis and the sequence alignment problem is well-studied for efficient bio sequence comparisons. We investigate the string matching problem allowing inversions: Given a pattern P and a text T, find all indices of matching substrings of T when non-overlapping inversions are allowed. We design an O(nm) algorithm using O(m) space, where n is the size of T and m is the size of P. The proposed algorithm improves the space complexity of the best-known algorithm, which runs in O(nm) time with O(m 2) space. We, furthermore, improve the algorithm and achieve O(max{n, min{nm,nm 5-t/2 }}) average runtime for an alphabet of size t, which is faster than O(nm) when t ≥ 4.

Original languageEnglish
Title of host publicationFrontiers in Algorithmics - 8th International Workshop, FAW 2014, Proceedings
PublisherSpringer Verlag
Number of pages10
ISBN (Print)9783319080154
Publication statusPublished - 2014
Event8th International Frontiers of Algorithmics Workshop, FAW 2014 - Zhangjiajie, China
Duration: 2014 Jun 282014 Jun 30

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8497 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other8th International Frontiers of Algorithmics Workshop, FAW 2014

Bibliographical note

Funding Information:
This research was supported by the Basic Science Research Program through NRF funded by MEST (2012R1A1A2044562).

Funding Information:
Kim was supported by NRF (National Research Foundation of Korea) Grant funded by the Korean Government (NRF-2013-Global Ph.D. Fellowship Program).

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Space-efficient approximate string matching allowing inversions in fast average time'. Together they form a unique fingerprint.

Cite this