<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-21T05:21:52Z</responseDate><request verb="GetRecord" identifier="oai:macsphere.mcmaster.ca:11375/29850" metadataPrefix="dim">https://prod-ms-be.lib.mcmaster.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:macsphere.mcmaster.ca:11375/29850</identifier><datestamp>2026-09-24T19:48:55Z</datestamp><setSpec>com_11375_271</setSpec><setSpec>col_11375_272</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:doc="http://www.lyncode.com/xoai" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Mhaskar, Neerja</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author">Liu, Chenge</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="department" lang="en_US">Computing and Software</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2024-06-07T18:20:49Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2024-06-07T18:20:49Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2024</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/11375/29850</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://doi.org/10.71548/12985</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en_US">A cover of a string w is a string u such that each letter of w occurs in some occurrences&#xd;
of u. In this thesis, we present the k-approximate maximal cover, where we allow for&#xd;
at most k mismatches at each occurrence of u in w, u is not required to cover the&#xd;
entire string and to compute the coverage we consider only the exact matches. Our&#xd;
ultimate objective is to find an approximate cover that encompasses the maximum&#xd;
number of exact positions covered while allowing for k mismatches. For this problem,&#xd;
we present an efficient algorithm that executes in O(n2kLave)-time, where n is the&#xd;
length of the given string and Lave is the average length of the longest common prefix&#xd;
between every substring and the original string with up to k mismatches allowed.&#xd;
To further broaden the scope of string analysis, we address two novel problems: the&#xd;
k-frequency cover and the k-border. The k-frequency cover problem seeks to identify&#xd;
the longest substring u of x, that has the maximum number of its k-approximate&#xd;
occurrences over all the other substrings in x. We propose an algorithm with a&#xd;
computational complexity of O(n2) to resolve this challenge efficiently. The longest&#xd;
k-border problem focuses on determining the longest prefix of string x that matches&#xd;
a suffix of x of the same length while allowing at most k mismatches. We propose an&#xd;
O(n2)-time algorithm to compute the longest k-border of every substring of x.</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="degreetype" lang="en_US">Thesis</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="degree" lang="en_US">Master of Science (MSc)</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="layabstract" lang="en_US">Regularities in strings have been studied for many years and play a crucial role in&#xd;
various fields, including biology, language theory, and compression theory. Periodicity&#xd;
has been one of the major problems studied in the field of string algorithms spanning&#xd;
several decades. Despite the advancements, accurately identifying various periodici-&#xd;
ties and quasi-periodicities within a string presents a notable challenge, particularly&#xd;
when the analysis must account for errors or inconsistencies. To address these com-&#xd;
plexities the notion of k-approximate periodicities has been introduced. This concept&#xd;
allows up to k mismatches between each occurrence of the periodicity in the original&#xd;
string, providing a more flexible approach to understanding string regularities. In&#xd;
this context, our work introduces innovative algorithms designed to efficiently com-&#xd;
pute the k-approximate maximal cover, k-frequency cover and longest k-border under&#xd;
the Hamming distance measure.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en_US">en</dim:field>
   <dim:field mdschema="dc" element="title" lang="en_US">Algorithms to Compute K-Approximate Periodicities</dim:field>
   <dim:field mdschema="dc" element="type" lang="en_US">Thesis</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim></metadata></record></GetRecord></OAI-PMH>