Repository logo
 

Space efficient string search algorithms and data structures

Date

2015

Authors

Deoghare, Pratik, author
McConnell, Ross, advisor
Bohm, Wim, advisor
Hulpke, Alexander, committee member

Journal Title

Journal ISSN

Volume Title

Abstract

We address the problem of finding all the occurrences of a pattern of length m in a text of length n. We introduce two new data structures, called the Sloppy Suffix Array and the Super Sloppy Suffix Array. These data structures are space efficient, easy to understand and implement. Sloppy suffix arrays can be built faster than suffix arrays with just one array of n integers; the search algorithms for both have the same time complexity of O(m log n). We also give a space efficient representation for positional de Bruijn graphs using suffix arrays.

Description

Rights Access

Subject

algorithm
data structure
space efficient
string search

Citation

Associated Publications