Search Results

Documents authored by Faro, Simone

Artifact
Software
DOI: 10.4230/artifacts.26165
marfra99x/SCER-ISM

Authors: Simone Faro, Dominik Köppl, Thierry Lecroq, and Francesco Pio Marino

Abstract
Cite as

Simone Faro, Dominik Köppl, Thierry Lecroq, Francesco Pio Marino. marfra99x/SCER-ISM (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-26165,
   title = {{marfra99x/SCER-ISM}}, 
   author = {Faro, Simone and K\"{o}ppl, Dominik and Lecroq, Thierry and Marino, Francesco Pio},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:c33fa1f2fdf35f4030601b03c54ad27d5931dfd0;origin=https://github.com/marfra99x/SCER-ISM;visit=swh:1:snp:516108321a19cbaf1c5afa4642e48da858bea6d1;anchor=swh:1:rev:733c4f4d2ed2b6b639e06205325ad9b699af5602}{\texttt{swh:1:dir:c33fa1f2fdf35f4030601b03c54ad27d5931dfd0}} (visited on 2026-06-08)},
   url = {https://github.com/marfra99x/SCER-ISM},
   doi = {10.4230/artifacts.26165},
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.21
A Bitwise Approach to SCER Matching in Indeterminate Strings

Authors: Simone Faro, Dominik Köppl, Thierry Lecroq, and Francesco Pio Marino

Published in: LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Abstract
We study the problem of matching a determinate pattern against an indeterminate text of the same length n, where each text position is a set of possible characters drawn from an alphabet Σ of size σ. We study this matching problem under the order-preserving and parameterized matching setting. For that, we encode character sets by bit expressions using sum-free sequences. This encoding enables constant-time character comparisons and avoids explicit set operations. We present an optimal 𝒪(n) time algorithm for order-preserving matching and an 𝒪(n+(σ_p^x ⋅ σ_p^y) √{σ_p^x + σ_p^y}) time algorithm for parameterized matching, where σ_p^x and σ_p^y denote the number of distinct parameterized symbols in the pattern and the text, respectively. The proposed techniques significantly reduce overhead while maintaining exactness, offering practical performance improvements for pattern matching under uncertainty. Additionally, we extend the parameterized matching framework to allow mismatches, for which we present an algorithm with time complexity 𝒪(σ² n log n + n σ² √σ log(n σ)).
Cite as

Simone Faro, Dominik Köppl, Thierry Lecroq, and Francesco Pio Marino. A Bitwise Approach to SCER Matching in Indeterminate Strings. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 21:1-21:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{faro_et_al:LIPIcs.CPM.2026.21,
  author =	{Faro, Simone and K\"{o}ppl, Dominik and Lecroq, Thierry and Marino, Francesco Pio},
  title =	{{A Bitwise Approach to SCER Matching in Indeterminate Strings}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{21:1--21:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.21},
  URN =		{urn:nbn:de:0030-drops-259470},
  doi =		{10.4230/LIPIcs.CPM.2026.21},
  annote =	{Keywords: string matching, indeterminate strings, SCER matching}
}
Document
DOI: 10.4230/LIPIcs.FUN.2026.15
Spells for Quantum Programmers: Expressive High-Level Commands in Qutes

Authors: Simone Faro, Francesco Pio Marino, and Gabriele Messina

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
Classical computers are powerful but fundamentally mundane: they operate through explicit, step-by-step instructions that force programmers to think locally and procedurally. Quantum technologies, by contrast, resemble magical instruments, capable of acting on superpositions, correlations, and entire collections of states at once. Yet, despite their magical nature, quantum computers are still programmed as if they were ordinary machines, relying on long sequences of low-level operations that obscure the underlying algorithmic ideas. Magic, however, is not performed by improvisation alone: it requires a spellbook. In this paper we position Qutes as a book of spells for quantum programmers, providing high-level commands that capture complex quantum behaviour behind concise and expressive syntax. We focus on the manipulation of quantum arrays, which naturally arise in many algorithms but are notoriously cumbersome to manage at the circuit level. We introduce three new array-oriented spells in Qutes: global initialization, parallel pairwise comparison, and parallel (optionally controlled) swap. Individually, these spells encapsulate non-trivial quantum procedures; when combined, they enable programmers to express algorithms in a way that is immediate, readable, and surprisingly elegant. As a final demonstration, we show how these spells can be assembled to produce a remarkably compact implementation of Bubble Sort. While algorithmically simple, this example illustrates a broader message: when the right abstractions are available, quantum programming can feel less like engineering machinery and more like magic.
Cite as

Simone Faro, Francesco Pio Marino, and Gabriele Messina. Spells for Quantum Programmers: Expressive High-Level Commands in Qutes. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 15:1-15:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{faro_et_al:LIPIcs.FUN.2026.15,
  author =	{Faro, Simone and Marino, Francesco Pio and Messina, Gabriele},
  title =	{{Spells for Quantum Programmers: Expressive High-Level Commands in Qutes}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{15:1--15:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.15},
  URN =		{urn:nbn:de:0030-drops-257349},
  doi =		{10.4230/LIPIcs.FUN.2026.15},
  annote =	{Keywords: Quantum programming languages, High-level abstractions, Quantum arrays}
}
Document
DOI: 10.4230/LIPIcs.SEA.2024.24
Efficient Exact Online String Matching Through Linked Weak Factors

Authors: Matthew N. Palmer, Simone Faro, and Stefano Scafiti

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
Online exact string matching is a fundamental computational problem in computer science, involving the sequential search for a pattern within a large text without prior access to the entire text. Its significance is underscored by its diverse applications in data compression, data mining, text editing, and bioinformatics, just to cite a few, where efficient substring matching is crucial. While the problem has been a subject of study for years, recent decades have witnessed a heightened focus on experimental solutions, employing various techniques to achieve superior performance. Notably, approaches centered around weak factor recognition have emerged as leaders in experimental settings, gaining increasing attention. This paper introduces Hash Chain, a novel algorithm founded on a robust weak factor recognition approach that links adjacent factors through hashing. Building upon the efficacy of weak recognition techniques, the proposed algorithm incorporates innovative strategies for organizing data structures and optimizations to enhance performance. Despite its quadratic worst-case time complexity, the new proposed algorithm demonstrates sublinear behavior in practice, outperforming currently known algorithms in the literature.
Cite as

Matthew N. Palmer, Simone Faro, and Stefano Scafiti. Efficient Exact Online String Matching Through Linked Weak Factors. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{palmer_et_al:LIPIcs.SEA.2024.24,
  author =	{Palmer, Matthew N. and Faro, Simone and Scafiti, Stefano},
  title =	{{Efficient Exact Online String Matching Through Linked Weak Factors}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{24:1--24:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.24},
  URN =		{urn:nbn:de:0030-drops-203896},
  doi =		{10.4230/LIPIcs.SEA.2024.24},
  annote =	{Keywords: String matching, text processing, weak recognition, hashing, experimental algorithms, design and analysis of algorithms}
}
Document
DOI: 10.4230/LIPIcs.FUN.2024.13
The Great Textual Hoax: Boosting Sampled String Matching with Fake Samples

Authors: Simone Faro, Francesco Pio Marino, Andrea Moschetto, Arianna Pavone, and Antonio Scardace

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract
Sampled String Matching is presented as an efficient solution to the string matching problem, aiming to tackle the space constraints of indexed string matching while purportedly reducing search times for online solutions. Despite the problem’s inception dating back to 1991, practical solutions have only recently emerged. These purportedly accelerate online searches by up to 35 times compared to conventional methods, achieved through a partial index occupying a mere 5% of the text size. This paper delves into the intricacies of one of the latest and most effective text sampling techniques, character distance sampling, which revolves around sampling distances between characters of a selected alphabet within the text. Specifically, we introduce fake samples while remaining honest! In other words, the study reveals that, interestingly, strategically introducing fake samples within the sampled sequence slashes the required index space by almost half, just avoid compromising the algorithm’s correctness. Additionally, since efficiency is everything, this approach, in turn, purportedly enhances the algorithm’s efficiency under specific conditions.
Cite as

Simone Faro, Francesco Pio Marino, Andrea Moschetto, Arianna Pavone, and Antonio Scardace. The Great Textual Hoax: Boosting Sampled String Matching with Fake Samples. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{faro_et_al:LIPIcs.FUN.2024.13,
  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}
}
Document
DOI: 10.4230/LIPIcs.WABI.2020.19
Sequence Searching Allowing for Non-Overlapping Adjacent Unbalanced Translocations

Authors: Domenico Cantone, Simone Faro, and Arianna Pavone

Published in: LIPIcs, Volume 172, 20th International Workshop on Algorithms in Bioinformatics (WABI 2020)

Abstract
Unbalanced translocations are among the most frequent chromosomal alterations, accounted for 30% of all losses of heterozygosity, a major genetic event causing inactivation of tumor suppressor genes. Despite of their central role in genomic sequence analysis, little attention has been devoted to the problem of matching sequences allowing for this kind of chromosomal alteration. In this paper we investigate the approximate string matching problem when the edit operations are non-overlapping unbalanced translocations of adjacent factors. In particular, we first present a 𝒪(nm³)-time and 𝒪(m²)-space algorithm based on the dynamic-programming approach. Then we improve our first result by designing a second solution which makes use of the Directed Acyclic Word Graph of the pattern. In particular, we show that under the assumptions of equiprobability and independence of characters, our algorithm has a 𝒪(nlog²_{σ} m) average time complexity, for an alphabet of size σ, still maintaining the 𝒪(nm³)-time and the 𝒪(m²)-space complexity in the worst case. To the best of our knowledge this is the first solution in literature for the approximate string matching problem allowing for unbalanced translocations of factors.
Cite as

Domenico Cantone, Simone Faro, and Arianna Pavone. Sequence Searching Allowing for Non-Overlapping Adjacent Unbalanced Translocations. In 20th International Workshop on Algorithms in Bioinformatics (WABI 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 172, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cantone_et_al:LIPIcs.WABI.2020.19,
  author =	{Cantone, Domenico and Faro, Simone and Pavone, Arianna},
  title =	{{Sequence Searching Allowing for Non-Overlapping Adjacent Unbalanced Translocations}},
  booktitle =	{20th International Workshop on Algorithms in Bioinformatics (WABI 2020)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-161-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{172},
  editor =	{Kingsford, Carl and Pisanti, Nadia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2020.19},
  URN =		{urn:nbn:de:0030-drops-128086},
  doi =		{10.4230/LIPIcs.WABI.2020.19},
  annote =	{Keywords: Text processing, approximate matching, inversions, sequence matching}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.SEA.2020
LIPIcs, Volume 160, SEA 2020, Complete Volume

Authors: Simone Faro and Domenico Cantone

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract
LIPIcs, Volume 160, SEA 2020, Complete Volume
Cite as

18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 1-366, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{faro_et_al:LIPIcs.SEA.2020,
  title =	{{LIPIcs, Volume 160, SEA 2020, Complete Volume}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{1--366},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020},
  URN =		{urn:nbn:de:0030-drops-120730},
  doi =		{10.4230/LIPIcs.SEA.2020},
  annote =	{Keywords: LIPIcs, Volume 160, SEA 2020, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.SEA.2020.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Simone Faro and Domenico Cantone

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{faro_et_al:LIPIcs.SEA.2020.0,
  author =	{Faro, Simone and Cantone, Domenico},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{0:i--0:xii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.0},
  URN =		{urn:nbn:de:0030-drops-120741},
  doi =		{10.4230/LIPIcs.SEA.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact