All-pairs suffix/prefix in optimal time using Aho-Corasick space

DOI10.1016/j.ipl.2022.106275OpenAlexW4225258327MaRDI QIDQ2169425

Solon P. Pissis, Grigorios Loukides

Publication date: 2 September 2022

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2022.106275

zbMATH Keywords

algorithmsdata structuresstring algorithmsAho-Corasick machinefailure transition tree

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Uses Software

• Readjoiner

Cites Work

• Unnamed Item
• Unnamed Item
• Construction of Aho Corasick automaton in linear time for integer alphabets
• A linear-time algorithm for finding approximate shortest common superstrings
• Efficient algorithms for the all-pairs suffix-prefix problem and the all-pairs substring-prefix problem
• An efficient algorithm for the all pairs suffix-prefix problem
• A fast algorithm for the all-pairs suffix-prefix problem
• Parallel computation for the all-pairs suffix-prefix problem
• Hierarchical overlap graph
• An improved algorithm for the all-pairs suffix-prefix problem
• Suffix Arrays: A New Method for On-Line String Searches
• Efficient string matching
• Algorithms on Strings, Trees and Sequences
• Algorithms on Strings

This page was built for publication: All-pairs suffix/prefix in optimal time using Aho-Corasick space