Validating the Knuth-Morris-Pratt failure function, fast and online

DOI10.1007/S00224-013-9522-8zbMath1380.68473OpenAlexW1999151208WikidataQ59394816 ScholiaQ59394816MaRDI QIDQ1678758

Łukasz Jeż, Artur Jeż, Paweł Gawrychowski

Publication date: 7 November 2017

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-013-9522-8

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Related Items (10)

Universal Reconstruction of a String ⋮ Inferring strings from Lyndon factorization ⋮ On Maximal Unbordered Factors ⋮ Recognizing union-find trees is NP-complete ⋮ Reconstructing a string from its Lyndon arrays ⋮ Reconstructing parameterized strings from parameterized suffix and LCP arrays ⋮ Recognizing Union-Find Trees is NP-Complete, Even Without Rank Info ⋮ Universal reconstruction of a string ⋮ A suffix tree or not a suffix tree? ⋮ String inference from longest-common-prefix array

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Verifying and enumerating parameterized border arrays
• On Simon's string searching algorithm
• Counting distinct strings
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths
• On-line construction of suffix trees
• Real-time recognition of the inclusion relation
• Cover Array String Reconstruction
• Counting Parameterized Border Arrays for a Binary Alphabet
• Efficient validation and construction of border arrays and validation of string matching automata
• A Space-Economical Suffix Tree Construction Algorithm
• Fast Pattern Matching in Strings
• On the Comparison Complexity of the String Prefix-Matching Problem
• Dynamic Perfect Hashing: Upper and Lower Bounds
• Jewels of Stringology
• Cuckoo hashing
• REVERSE ENGINEERING PREFIX TABLES
• Algorithms on Strings
• String matching algorithms and automata

This page was built for publication: Validating the Knuth-Morris-Pratt failure function, fast and online