Author name cluster

Simone Faro

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

1 author row

TCS Journal 2026 Journal Article

Quantum algorithms for longest common and palindromic substrings in the circuit model

Domenico Cantone
Simone Faro
Arianna Pavone
Caterina Viola

The Longest Common Substring (LCS) and Longest Palindromic Substring (LPS) problems are fundamental challenges in string processing, traditionally solved in linear time using classical computation through suffix trees. Recent breakthroughs by Le Gall and Seddighin [1] introduced sublinear quantum query algorithms, while Akmal and Jin [2] further improved the LCS complexity to O ˜ ( n 2 / 3 ). While these results are remarkable in the quantum query model, their practical implementation on real quantum hardware remains elusive. In this paper, we bridge this gap by presenting the first O ˜ ( n ) quantum algorithms for both LCS and LPS in the circuit model of computation. Our circuits are explicitly constructed and analyzed in terms of size and depth, achieving polylogarithmic overheads while preserving the O ˜ ( n ) depth bound. This provides, for the first time, concrete circuit-level blueprints and resource estimates for quantum solutions to LCS and LPS.

Details DOI

TCS Journal 2023 Journal Article

Compact suffix automata representations for searching long patterns

Simone Faro
Stefano Scafiti

Automata based algorithms have always dominated the history of string matching, thanks to their intrinsic nature of recognizers. Among them, those based on the suffix automaton deserve a special mention, because its use has always led to elegant and very efficient solutions in practice. In this paper, we present two novel string matching algorithms based on the suffix automaton which are particularly suitable for very long strings. The first algorithm simulates the suffix automaton through the well known bit-parallelism approach, while the second makes use of an alternative non-standard simulation. We mainly focus on the second solution, which turns out to be more flexible in practice, and present some extensions of it. Experimental results suggest that both our solutions are very efficient in practical cases scaling much better when the length of the pattern increases. Moreover, our second approach is also competitive with the most effective solutions available for the exact string matching problem.

Details DOI

TCS Journal 2023 Journal Article

Improved characters distance sampling for online and offline text searching

Simone Faro
Francesco Pio Marino
Arianna Pavone

Sampled string matching is a very effective technique to reduce the search time for a pattern within a text at the cost of a small amount of additional memory, used for storing a partial index of the text. This approach has recently received some interest and has been applied to improve both online and offline string matching solutions, improving standard solutions by more than 50%. However, this improvement is currently only achievable in the case of texts on large-sized alphabets, and remains small (or absent) in the case of small-sized alphabets. In this article we propose an extension of the approach to text-sampling, known as Character Distance Sampling, to the case of small alphabets, obtaining an improvement of up to 98% compared to standard solutions in the case of online string matching. We also extend this approach to the case of offline string matching, introducing a sampled version of the suffix array, obtaining performances up to 5 times higher than the search obtained on the standard suffix array. Differently from what has been done by previous solutions, our idea is not based on the reduction of the number of indexed suffixes, but on the construction of the index directly on the sampled text.

Details DOI

TCS Journal 2022 Journal Article

A weak approach to suffix automata simulation for exact and approximate string matching

Simone Faro
Stefano Scafiti

String matching is one of the most extensively studied problems in computer science, mainly due to its direct applications to such diverse areas as text, image and signal processing, speech analysis and recognition, information retrieval, data compression, computational biology and chemistry. In the last few decades a myriad of alternative solutions have been proposed, based on very different techniques. However, automata have always played a very important role in the design of efficient string matching algorithms. In this paper we present the Range Automaton, a weak yet efficient variant of the non-deterministic suffix automaton of a string whose configuration can be encoded in a very simple form and which is particularly suitable to be used for solving a multitude of text-searching problems. We will firstly develop our approach in the case of exact string matching and present an efficient algorithm, named Backward Range Automaton Matcher, which turns out to be very fast in many practical cases. Later, we will show how the Range Automaton can be adapted in an effective way also to non-standard string matching problems such as swap matching and multiple string matching. Experimental results suggest that our approach is flexible and effective for all three search problems addressed, especially in the case of long patterns.

Details DOI

TCS Journal 2021 Journal Article

Fast algorithms for single and multiple pattern Cartesian tree matching

Siwoo Song
Geonmo Gu
Cheol Ryu
Simone Faro
Thierry Lecroq
Kunsoo Park

Cartesian tree matching is the problem of finding every substring of a given text which has the same Cartesian tree as that of a given pattern. In this paper we propose fast algorithms for single and multiple pattern Cartesian tree matching by introducing new representations and encodings. For single pattern Cartesian tree matching, we present the framework of a binary filtration method and an efficient verification technique. Any exact string matching algorithm can be used as a filtration for Cartesian tree matching in our framework. For multiple pattern Cartesian tree matching, we present two fingerprinting methods, i. e. , the parent-distance encoding and the binary encoding. By combining an efficient fingerprinting method and a conventional multiple string matching algorithm, we can efficiently solve multiple pattern Cartesian tree matching. By experiments we show that our matching algorithms provide good performances for both single and multiple pattern Cartesian tree matching.

Details DOI

TCS Journal 2013 Journal Article

Efficient string-matching allowing for non-overlapping inversions

Domenico Cantone
Salvatore Cristofaro
Simone Faro

Inversions are a class of chromosomal mutations, widely regarded as one of the major mechanisms for reorganizing the genome. In this paper we present a new algorithm for the approximate string matching problem allowing for non-overlapping inversions which runs in O ( n m ) worst-case time and O ( m 2 ) space, for a character sequence of size n and pattern of size m. This improves upon a previous O ( n m 2 ) -time algorithm. In addition we present a variant of our algorithm with the same complexity in the worst case, but with a O ( n ) time complexity in the average case.

Details DOI

I&C Journal 2012 Journal Article

A compact representation of nondeterministic (suffix) automata for the bit-parallel approach

Domenico Cantone
Simone Faro
Emanuele Giaquinta

We present a novel technique, suitable for bit-parallelism, for representing both the nondeterministic automaton and the nondeterministic suffix automaton of a given string in a more compact way. Our approach is based on a particular factorization of strings which on the average allows to pack in a machine word of w bits automata state configurations for strings of length greater than w. We adapted the Shift-And and BNDM algorithms using our encoding and compared them with the original algorithms. Experimental results show that the new variants are generally faster for long patterns.

Details DOI