{"id":{"repo_id":"mcmaster","oai_identifier":"oai:macsphere.mcmaster.ca:11375/32683"},"canonical_url":"https://search.ndltd.org/etd/mcmaster/oai:macsphere.mcmaster.ca:11375/32683","repository":{"repo_id":"mcmaster","name":"McMaster University","base_url":"https://macsphere.mcmaster.ca/server/oai/request"},"display":{"title":"EFFICIENT COMPUTATION OF CLOSED SUBSTRINGS","abstract":"A \\df{closed string} $ u $ is either of length one or contains a border that occurs only as a prefix and as a suffix of $ u $, without appearing elsewhere within $ u $. This thesis presents a fast and practical $ \\mathcal{O}(n \\log n) $ time algorithm to compute all $ \\mathcal{O}(n^2) $ closed substrings of a string $ w[1..n] $. This is achieved by introducing a compact representation of all closed substrings using only $ \\mathcal{O}(n \\log n) $ space. Additionally, a simple and space-efficient approach is proposed to compute all maximal closed substrings (MCSs) using the suffix array ($\\mathsf{SA}$) and the longest common prefix ($\\mathsf{LCP}$) array of $ w[1..n] $. Given a Fibonacci word $f_n$, where $n>5$, the thesis shows that the exact number of MCSs is $ M(f_n) \\approx \\left(1 + \\frac{1}{\\phi^2}\\right) F_n \\approx 1.382 F_n $, where $ \\phi $ is the golden ratio, and $ F_n $ is the $ n $-th Fibonacci number. These results highlight novel combinatorial properties of closed substrings in structured sequences. To complement the theoretical findings, an efficient implementation of the algorithms for computing closed strings and MCSs is provided. The implementation has been thoroughly tested and is designed to support practical applications, facilitating further exploration of closed substrings in various contexts.","abstract_html":"A \\df{closed string} $ u $ is either of length one or contains a border that occurs only as a prefix and as a suffix of $ u $, without appearing elsewhere within $ u $. This thesis presents a fast and practical $ \\mathcal{O}(n \\log n) $ time algorithm to compute all <span class=\"etd-inline-math\"> \\mathcal{O}(n<sup>2</sup>) </span> closed substrings of a string $ w[1..n] $. This is achieved by introducing a compact representation of all closed substrings using only $ \\mathcal{O}(n \\log n) $ space. Additionally, a simple and space-efficient approach is proposed to compute all maximal closed substrings (MCSs) using the suffix array ($\\mathsf{SA}$) and the longest common prefix ($\\mathsf{LCP}$) array of $ w[1..n] $. Given a Fibonacci word <span class=\"etd-inline-math\">f<sub>n</sub></span>, where $n&gt;5$, the thesis shows that the exact number of MCSs is <span class=\"etd-inline-math\"> M(f<sub>n</sub>) \\approx \\left(1 + \\frac{1}{\\phi<sup>2</sup>}\\right) F<sub>n</sub> \\approx 1.382 F<sub>n</sub> </span>, where $ \\phi $ is the golden ratio, and <span class=\"etd-inline-math\"> F<sub>n</sub> </span> is the $ n $-th Fibonacci number. These results highlight novel combinatorial properties of closed substrings in structured sequences. To complement the theoretical findings, an efficient implementation of the algorithms for computing closed strings and MCSs is provided. The implementation has been thoroughly tested and is designed to support practical applications, facilitating further exploration of closed substrings in various contexts.","abstract_has_math":true,"creators":["Samkith K Jain"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2026,"date_issued":"2026","date_published":"2026","updated_at":"2026-11-18T19:37:20Z","subjects":["Closed Strings","Maximal Closed Substrings","Fibonacci Words"],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://doi.org/10.71548/18342"],"render_values":[{"text":"https://doi.org/10.71548/18342","href":"https://doi.org/10.71548/18342","code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/11375/32683","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/11375/32683","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://macsphere.mcmaster.ca/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Amacsphere.mcmaster.ca%3A11375%2F32683","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Samkith K Jain"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2025-12-15T20:29:28Z"]},{"key":"dc:date.issued","label":"Date","values":["2026"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Closed Strings","Maximal Closed Substrings","Fibonacci Words"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/11375/32683","https://doi.org/10.71548/18342"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["A \\df{closed string} $ u $ is either of length one or contains a border that occurs only as a prefix and as a suffix of $ u $, without appearing elsewhere within $ u $. This thesis presents a fast and practical $ \\mathcal{O}(n \\log n) $ time algorithm to compute all $ \\mathcal{O}(n^2) $ closed substrings of a string $ w[1..n] $. This is achieved by introducing a compact representation of all closed substrings using only $ \\mathcal{O}(n \\log n) $ space. Additionally, a simple and space-efficient approach is proposed to compute all maximal closed substrings (MCSs) using the suffix array ($\\mathsf{SA}$) and the longest common prefix ($\\mathsf{LCP}$) array of $ w[1..n] $. Given a Fibonacci word $f_n$, where $n>5$, the thesis shows that the exact number of MCSs is $ M(f_n) \\approx \\left(1 + \\frac{1}{\\phi^2}\\right) F_n \\approx 1.382 F_n $, where $ \\phi $ is the golden ratio, and $ F_n $ is the $ n $-th Fibonacci number. These results highlight novel combinatorial properties of closed substrings in structured sequences. To complement the theoretical findings, an efficient implementation of the algorithms for computing closed strings and MCSs is provided. The implementation has been thoroughly tested and is designed to support practical applications, facilitating further exploration of closed substrings in various contexts."]},{"key":"dc:title","label":"Title","values":["EFFICIENT COMPUTATION OF CLOSED SUBSTRINGS"]},{"key":"dc:title.alternative","label":"Alternative Title","values":["CLOSED STRINGS"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"dc:creator":["Samkith K Jain"],"dc:date.accessioned":["2025-12-15T20:29:28Z"],"dc:date.issued":["2026"],"dc:description.abstract":["A \\df{closed string} $ u $ is either of length one or contains a border that occurs only as a prefix and as a suffix of $ u $, without appearing elsewhere within $ u $. This thesis presents a fast and practical $ \\mathcal{O}(n \\log n) $ time algorithm to compute all $ \\mathcal{O}(n^2) $ closed substrings of a string $ w[1..n] $. This is achieved by introducing a compact representation of all closed substrings using only $ \\mathcal{O}(n \\log n) $ space. Additionally, a simple and space-efficient approach is proposed to compute all maximal closed substrings (MCSs) using the suffix array ($\\mathsf{SA}$) and the longest common prefix ($\\mathsf{LCP}$) array of $ w[1..n] $. Given a Fibonacci word $f_n$, where $n>5$, the thesis shows that the exact number of MCSs is $ M(f_n) \\approx \\left(1 + \\frac{1}{\\phi^2}\\right) F_n \\approx 1.382 F_n $, where $ \\phi $ is the golden ratio, and $ F_n $ is the $ n $-th Fibonacci number. These results highlight novel combinatorial properties of closed substrings in structured sequences. To complement the theoretical findings, an efficient implementation of the algorithms for computing closed strings and MCSs is provided. The implementation has been thoroughly tested and is designed to support practical applications, facilitating further exploration of closed substrings in various contexts."],"dc:identifier.uri":["https://hdl.handle.net/11375/32683","https://doi.org/10.71548/18342"],"dc:language.iso":["en"],"dc:subject":["Closed Strings","Maximal Closed Substrings","Fibonacci Words"],"dc:title":["EFFICIENT COMPUTATION OF CLOSED SUBSTRINGS"],"dc:title.alternative":["CLOSED STRINGS"],"dc:type":["Thesis"],"others:access_status":["open.access"]},"updated_at":"2026-11-18T19:37:20Z"}