Papers | Francesco Pio Marino

2024

ICTCS

Improving Sampled Matching through Character Context Sampling

Simone Faro, Thierry Lecroq, Francesco Pio Marino, and 2 more authors

In Proceedings of the 25nd Italian Conference on Theoretical Computer Science, Torino, Italy, September 11-13, 2024, 2024

Bib HTML

@inproceedings{FaroLMPS24,
  author = {Faro, Simone and Lecroq, Thierry and Marino, Francesco Pio and Pavone, Arianna and Scafiti, Stefano},
  title = {Improving Sampled Matching through Character Context Sampling},
  booktitle = {Proceedings of the 25nd Italian Conference on Theoretical Computer
                    Science, Torino, Italy, September 11-13, 2024},
  series = {{CEUR} Workshop Proceedings},
  publisher = {CEUR-WS.org},
  year = {2024},
  url = {http://ictcs2024.di.unito.it/wp-content/uploads/2024/08/ICTCS_2024_paper_22.pdf},
}

PSC

Beyond Horspool: A Comparative Analysis in Sampled Matching

Simone Faro, Francesco Pio Marino, and Andrea Moschetto

In Prague Stringology Conference 2024, Prague, Czech Republic, August 26-27, 2024, 2024

Bib

@inproceedings{PSC24FMM,
  author = {Faro, Simone and Marino, Francesco Pio and Moschetto, Andrea},
  title = {Beyond {H}orspool: A Comparative Analysis in Sampled Matching},
  editor = {Holub, Jan and Zd{\'{a}}rek, Jan},
  booktitle = {Prague Stringology Conference 2024, Prague, Czech Republic, August
                    26-27, 2024},
  publisher = {Czech Technical University in Prague, Faculty of Information Technology,
                    Department of Theoretical Computer Science},
  year = {2024},
}

FUN

The Great Textual Hoax: Boosting Sampled String Matching with Fake Samples

Simone Faro, Francesco Pio Marino, Andrea Moschetto, and 2 more authors

In 12th International Conference on Fun with Algorithms (FUN 2024), 2024

Bib HTML

@inproceedings{FUN24FMMPS,
  author = {Faro, Simone and Marino, Francesco Pio and Moschetto, Andrea and Pavone, Arianna and Scardace, Antonio},
  title = {{The Great Textual Hoax: Boosting Sampled String Matching with Fake Samples}},
  booktitle = {12th International Conference on Fun with Algorithms (FUN 2024)},
  pages = {13:1--13:17},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  isbn = {978-3-95977-314-0},
  issn = {1868-8969},
  year = {2024},
  volume = {291},
  editor = {Broder, Andrei Z. and Tamir, Tami},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address = {Dagstuhl, Germany},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.13},
  urn = {urn:nbn:de:0030-drops-199211},
  doi = {10.4230/LIPIcs.FUN.2024.13},
  annote = {Keywords: string matching, sampling},
  google_scholar_id = {Tyk-4Ss8FVUC},
}

QUASAR

Practical Implementation of a Quantum String Matching Algorithm

Francesco Pio Marino, Simone Faro, and Antonio Scardace

In Proceedings of the 2024 Workshop on Quantum Search and Information Retrieval, Pisa, Italy, 2024

Bib HTML

@inproceedings{MFS24,
  author = {Marino, Francesco Pio and Faro, Simone and Scardace, Antonio},
  title = {Practical Implementation of a Quantum String Matching Algorithm},
  year = {2024},
  isbn = {9798400706462},
  publisher = {Association for Computing Machinery},
  address = {New York, NY, USA},
  url = {https://doi.org/10.1145/3660318.3660327},
  doi = {10.1145/3660318.3660327},
  booktitle = {Proceedings of the 2024 Workshop on Quantum Search and Information Retrieval},
  pages = {17–24},
  numpages = {8},
  keywords = {string matching, quantum computing, text processing, quantum search},
  location = {Pisa, Italy},
  series = {QUASAR '24},
}

FTC

Practical Quantum Combinatorial String Matching

Domenico Cantone, Claudio Caudullo, Simone Faro, and 3 more authors

In Proceedings of the Future Technologies Conference (FTC) 2024, Volume 3, 2024

Abs

This paper focuses on the practical implementation of quantum computation for various combinatorial problems in strings. We provide a detailed description of all the operators involved in solving the problems addressed in this paper, along with practical implementation details of our solution. The algorithms developed for quantum computation provide polylogarithmic solutions, showcasing a complexity improvement compared to classical solutions, with the best results achieving linear complexity.

Pre-print

Fast computation of the period and of the shortest cover of a string using its Character-Distance-Sampling representation

Thierry Lecroq, and Francesco Pio Marino

2024

Bib HTML

@article{PSC24LM,
  title = {Fast computation of the period and of the shortest cover of a string using its Character-Distance-Sampling representation},
  author = {Lecroq, Thierry and Marino, Francesco Pio},
  year = {2024},
  eprint = {2407.18216},
  archiveprefix = {arXiv},
  primaryclass = {cs.DS},
  url = {https://arxiv.org/abs/2407.18216},
}

2023

TCS

Improved characters distance sampling for online and offline text searching

Simone Faro, Francesco Pio Marino, and Arianna Pavone

Theor. Comput. Sci., 2023

Bib HTML

@article{FaroMP23,
  author = {Faro, Simone and Marino, Francesco Pio and Pavone, Arianna},
  title = {Improved characters distance sampling for online and offline text
                    searching},
  journal = {Theor. Comput. Sci.},
  volume = {946},
  pages = {113684},
  year = {2023},
  url = {https://doi.org/10.1016/j.tcs.2022.12.034},
  doi = {10.1016/J.TCS.2022.12.034},
  timestamp = {Tue, 28 Mar 2023 19:51:03 +0200},
  biburl = {https://dblp.org/rec/journals/tcs/FaroMP23.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  google_scholar_id = {zYLM7Y9cAGgC},
}

2021

PSC

Towards an Efficient Text Sampling Approach for Exact and Approximate Matching

Simone Faro, Francesco Pio Marino, Arianna Pavone, and 1 more author

In Prague Stringology Conference 2021, Prague, Czech Republic, August 30-31, 2021, 2021

Bib

@inproceedings{FaroMPS21,
  author = {Faro, Simone and Marino, Francesco Pio and Pavone, Arianna and Scardace, Antonio},
  editor = {Holub, Jan and Zd{\'{a}}rek, Jan},
  title = {Towards an Efficient Text Sampling Approach for Exact and Approximate
                    Matching},
  booktitle = {Prague Stringology Conference 2021, Prague, Czech Republic, August
                    30-31, 2021},
  pages = {75--89},
  publisher = {Czech Technical University in Prague, Faculty of Information Technology,
                    Department of Theoretical Computer Science},
  year = {2021},
  url = {http://www.stringology.org/event/2021/p07.html},
  timestamp = {Wed, 31 Jan 2024 17:00:02 +0100},
  biburl = {https://dblp.org/rec/conf/stringology/FaroMPS21.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
}

ICTCS

Enhancing Characters Distance Text Sampling by Condensed Alphabets

Simone Faro, Francesco Pio Marino, and Arianna Pavone

In Proceedings of the 22nd Italian Conference on Theoretical Computer Science, Bologna, Italy, September 13-15, 2021, 2021

Bib

@inproceedings{FaroMP21,
  author = {Faro, Simone and Marino, Francesco Pio and Pavone, Arianna},
  editor = {Coen, Claudio Sacerdoti and Salvo, Ivano},
  title = {Enhancing Characters Distance Text Sampling by Condensed Alphabets},
  booktitle = {Proceedings of the 22nd Italian Conference on Theoretical Computer
                    Science, Bologna, Italy, September 13-15, 2021},
  series = {{CEUR} Workshop Proceedings},
  volume = {3072},
  pages = {1--15},
  publisher = {CEUR-WS.org},
  year = {2021},
  url = {https://ceur-ws.org/Vol-3072/paper1.pdf},
  timestamp = {Fri, 10 Mar 2023 16:23:17 +0100},
  biburl = {https://dblp.org/rec/conf/ictcs/FaroMP21.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
}

2020

Algorithmica

Efficient Online String Matching Based on Characters Distance Text Sampling

Simone Faro, Francesco Pio Marino, and Arianna Pavone

Algorithmica, 2020

Bib HTML

@article{FaroMP20,
  author = {Faro, Simone and Marino, Francesco Pio and Pavone, Arianna},
  title = {Efficient Online String Matching Based on Characters Distance Text
                    Sampling},
  journal = {Algorithmica},
  volume = {82},
  number = {11},
  pages = {3390--3412},
  year = {2020},
  url = {https://doi.org/10.1007/s00453-020-00732-4},
  doi = {10.1007/S00453-020-00732-4},
  timestamp = {Sun, 04 Aug 2024 19:48:50 +0200},
  biburl = {https://dblp.org/rec/journals/algorithmica/FaroMP20.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  google_scholar_id = {u5HHmVD_uO8C},
}

PSC

Reducing Time and Space in Indexed String Matching by Characters Distance Text Sampling

Simone Faro, and Francesco Pio Marino

In Prague Stringology Conference 2020, Prague, Czech Republic, August 31 - September 2, 2020, 2020

Bib

@inproceedings{FaroM20,
  author = {Faro, Simone and Marino, Francesco Pio},
  editor = {Holub, Jan and Zd{\'{a}}rek, Jan},
  title = {Reducing Time and Space in Indexed String Matching by Characters Distance
                    Text Sampling},
  booktitle = {Prague Stringology Conference 2020, Prague, Czech Republic, August
                    31 - September 2, 2020},
  pages = {148--159},
  publisher = {Czech Technical University in Prague, Faculty of Information Technology,
                    Department of Theoretical Computer Science},
  year = {2020},
  url = {http://www.stringology.org/event/2020/p13.html},
  timestamp = {Wed, 10 Feb 2021 08:42:19 +0100},
  biburl = {https://dblp.org/rec/conf/stringology/FaroM20.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
}

SOFSEM

Fast-Insertion-Sort: a New Family of Efficient Variants of the Insertion-Sort Algorithm

Simone Faro, Francesco Pio Marino, and Stefano Scafiti

In Proceedings of the SOFSEM 2020 Doctoral Student Research Forum co-located with the 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2020), Limassol, Cyprus, January 20-24, 2020, 2020