Efficient validation and construction of border arrays and validation of string matching automata

DOI10.1051/ita:2008030zbMath1166.68033OpenAlexW2162463605MaRDI QIDQ3625694

Arnaud Lefebvre, Thierry Lecroq, Jean-Pierre Duval

Publication date: 6 May 2009

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2009__43_2_281_0/

zbMATH Keywords

string matchingperiodcombinatorics on wordsborderstring matching automata

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Combinatorics on words (68R15) Formal languages and automata (68Q45)

Related Items (12)

Universal Reconstruction of a String ⋮ Inferring strings from Lyndon factorization ⋮ Validating the Knuth-Morris-Pratt failure function, fast and online ⋮ Recognizing union-find trees is NP-complete ⋮ Inferring strings from position heaps in linear time ⋮ Combinatorics on partial word borders ⋮ Representing prefix and border tables: results on enumeration ⋮ Inferring strings from suffix trees and links on a binary alphabet ⋮ 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

• Counting distinct strings
• Fast Pattern Matching in Strings
• Algorithms on Strings
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Efficient validation and construction of border arrays and validation of string matching automata