Back to search

UNF Digital Commons

Approximate String Matching With Dynamic Programming and Suffix Trees

Abstract

dc:description.abstract

The importance and the contribution of string matching algorithms to the modern society cannot be overstated. From basic search algorithms such as spell checking and data querying, to advanced algorithms such as DNA sequencing, trend analysis and signal processing, string matching algorithms form the foundation of many aspects in computing that have been pivotal in technological advancement. In general, string matching algorithms can be divided into the categories of exact string matching and approximate string matching. We study each area and examine some of the well known algorithms. We probe into one of the most intriguing data structure in string algorithms, the suffix tree. The lowest common ancestor extension of the suffix tree is the key to many advanced string matching algorithms. With these tools, we are able to solve string problems that were, until recently, thought intractable by many. Another interesting and relatively new data structure in string algorithms is the suffix array, which has significant breakthroughs in its linear time construction in recent years. Primarily, this thesis focuses on approximate string matching using dynamic programming and hybrid dynamic programming with suffix tree. We study both approaches in detail and see how the merger of exact string matching and approximate string matching algorithms can yield synergistic results in our experiments.

Degree

thesis:*
Name thesis:degree_name
Master of Science in Computer and Information Sciences (MS)
Discipline thesis:degree_discipline
Computing
Grantor dc:publisher
UNF Digital Commons

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Keng, Leng Hui
Contributors dc:contributor
  • Dr. Yap S. Chua
  • Dr. Roger E. Eggen
  • Dr. William F. Klostermeyer

Subjects

dc:subject × 5

Rights

dc:rights

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.unf.edu/etd/196

Chain of custody

source
Harvested from
University of North Florida
Base URL
digitalcommons.unf.edu/do/oai/
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Keng, Leng Hui. Approximate String Matching With Dynamic Programming and Suffix Trees. UNF Digital Commons, https://digitalcommons.unf.edu/etd/196