Back to search

McMaster University

PATTERN MATCHING ON INDETERMINATE STRINGS WITH PREFIX ARRAYS

Abstract

dc:description.abstract

Uncertainty is prevalent in diverse datasets. This uncertainty is modelled by a string generalization termed as indeterminate string – a string containing one or more sub- sets of the alphabet as letters (known as indeterminate letters). In this thesis we revisit the pattern matching problem on indeterminate strings. We introduce innovative algorithms leveraging established techniques like KMP and BM, coupled with an exhaustive experimental evaluation focusing on both time complexity and runtime performance. Additionally, the thesis explores a novel encoding methodology for indeterminate strings, assessing its impact on runtime efficiency. Through rigorous analysis and experimentation, this study not only expands the theoretical framework of indeterminate pattern matching but also provides practical insights that will impact data processing in real-world applications.

Degree

thesis:*
Department dc:contributor.department
Computing and Software
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Dehghani, Hossein
Advisor dc:contributor.advisor
  • Mhaskar, Neerja

Subjects

dc:subject × 2

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Dehghani, Hossein. PATTERN MATCHING ON INDETERMINATE STRINGS WITH PREFIX ARRAYS. 2024. http://hdl.handle.net/11375/29309