Papers

2026

1. Access

   Optimal Character Distance Sampling for Exact String Matching Through Set Cover Reformulation

   Simone Faro, Thierry Lecroq, and Francesco Pio Marino

   IEEE Access, 2026

   Bib HTML

   @article{FaroLM26,
     author = {Faro, Simone and Lecroq, Thierry and Marino, Francesco Pio},
     title = {Optimal Character Distance Sampling for Exact String Matching Through Set Cover Reformulation},
     journal = {{IEEE} Access},
     volume = {14},
     pages = {13910--13920},
     year = {2026},
     doi = {10.1109/ACCESS.2026.3654667},
   }

2. TCJ

   Extending Qutes: a practical high-level language for quantum computing

   Simone Faro, Francesco Pio Marino, and Gabriele Messina

   Comput. J., 2026

   Bib HTML

   @article{FaroMM26,
     author = {Faro, Simone and Marino, Francesco Pio and Messina, Gabriele},
     title = {Extending Qutes: a practical high-level language for quantum computing},
     journal = {Comput. J.},
     volume = {69},
     number = {3},
     pages = {597--612},
     year = {2026},
     doi = {10.1093/COMJNL/BXAF133},
   }

3. DCC

   Attractor Matching: A New Paradigm for Structural String Comparison

   Simone Faro, Dominik Köppl, and Francesco Pio Marino

   In 2026 Data Compression Conference (DCC) 2026, Snowbird, UT - USA,, 2026

   Bib

   @inproceedings{FKM26,
     author = {Faro, Simone and K\"{o}ppl, Dominik and Marino, Francesco Pio},
     title = {Attractor Matching: A New Paradigm for Structural String Comparison},
     year = {2026},
     isbn = {},
     publisher = {IEEE},
     address = {},
     url = {},
     doi = {},
     booktitle = {2026 Data Compression Conference (DCC) 2026},
     pages = {},
     numpages = {},
     keywords = {},
     location = {Snowbird, UT - USA,},
     series = {DCC '26},
   }

4. DCC

   Enabling FM-Index for Elastic-Degenerate Strings via a new Min/Max Wavelet Tree

   Simone Faro, Thierry Lecroq, Dominik Köppl, and 1 more author

   In 2026 Data Compression Conference (DCC) 2026, Snowbird, UT - USA,, 2026

   Bib

   @inproceedings{FKLM26,
     author = {Faro, Simone and Lecroq, Thierry and K\"{o}ppl, Dominik and Marino, Francesco Pio},
     title = {Enabling FM-Index for Elastic-Degenerate Strings via a new Min/Max Wavelet Tree},
     year = {2026},
     isbn = {},
     publisher = {IEEE},
     address = {},
     url = {},
     doi = {},
     booktitle = {2026 Data Compression Conference (DCC) 2026},
     pages = {},
     numpages = {},
     keywords = {},
     location = {Snowbird, UT - USA,},
     series = {DCC '26},
   }

5. CPM

   A Bitwise Approach to SCER Matching in Indeterminate Strings

   Simone Faro, Thierry Lecroq, Dominik Köppl, and 1 more author

   In 37th Annual Symposium on Combinatorial Pattern Matching, Copenhagen, Denmark, 2026

   Bib

   @inproceedings{FKLM26CPM,
     author = {Faro, Simone and Lecroq, Thierry and K\"{o}ppl, Dominik and Marino, Francesco Pio},
     title = {A Bitwise Approach to SCER Matching in Indeterminate Strings},
     year = {2026},
     isbn = {},
     publisher = {},
     address = {},
     url = {},
     doi = {},
     booktitle = {37th Annual Symposium on Combinatorial Pattern Matching},
     pages = {},
     numpages = {},
     keywords = {},
     location = {Copenhagen, Denmark},
     series = {CPM '26},
   }

6. FUN

   Spells for Quantum Programmers: Expressive High-Level Commands in Qutes

   Simone Faro, Francesco Pio Marino, and Gabriele Messina

   In 13th International Conference on Fun with Algorithms, Island of Porquerolles, France, 2026

   Bib

   @inproceedings{FMM26,
     author = {Faro, Simone and Marino, Francesco Pio and Messina, Gabriele},
     title = {Spells for Quantum Programmers: Expressive High-Level Commands in Qutes},
     year = {2026},
     isbn = {},
     publisher = {},
     address = {},
     url = {},
     doi = {},
     booktitle = {13th International Conference on Fun with Algorithms},
     pages = {},
     numpages = {},
     keywords = {},
     location = {Island of Porquerolles, France},
     series = {FUN '26},
   }

2025

1. HPDC

   Scaling Grover’s Search for Large Solution Spaces

   Simone Faro, and Francesco Pio Marino

   In Proceedings of the 34th International Symposium on High-Performance, South Bend, IN - USA, 2025

   Bib

   @inproceedings{FM25,
     author = {Faro, Simone and Marino, Francesco Pio},
     title = {Scaling Grover's Search for Large Solution Spaces},
     year = {2025},
     isbn = {},
     publisher = {Association for Computing Machinery},
     address = {New York, NY, USA},
     url = {},
     doi = {},
     booktitle = {Proceedings of the 34th International Symposium on High-Performance},
     pages = {},
     numpages = {},
     keywords = {},
     location = {South Bend, IN - USA},
     series = {HPDC '25},
   }

2. HPDC

   Qutes: A High-Level Quantum Programming Language for Simplified Quantum Computing

   Simone Faro, Francesco Pio Marino, and Gabriele Messina

   In Proceedings of the 34th International Symposium on High-Performance, South Bend, IN - USA, 2025

   Bib

   @inproceedings{FMM25,
     author = {Faro, Simone and Marino, Francesco Pio and Messina, Gabriele},
     title = {Qutes: A High-Level Quantum Programming Language for Simplified Quantum Computing},
     year = {2025},
     isbn = {},
     publisher = {Association for Computing Machinery},
     address = {New York, NY, USA},
     url = {},
     doi = {},
     booktitle = {Proceedings of the 34th International Symposium on High-Performance},
     pages = {},
     numpages = {},
     keywords = {},
     location = {South Bend, IN - USA},
     series = {HPDC '25},
   }

2024

1. 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},
   }

2. 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},
   }

3. 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},
   }

4. 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},
   }

5. 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.

6. Pre-print

   Efficient Computation of Periods and Covers Using Sampling

   Thierry Lecroq, and Francesco Pio Marino

   2024

   Bib HTML

   @article{PrePrint24LM,
     title = {Efficient Computation of Periods and Covers Using Sampling},
     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

1. 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

1. 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},
   }

2. 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

1. 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},
   }

2. 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},
   }

3. 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