Loading...
Practical Implementation of a Quantum String Matching Algorithm
Association for Computing Machinery (HPDC - QUASAR 24) • doi.org/10.1145/3660318.3660327
This article presents a first practical implementation of a quantum circuit tailored to address string matching, particularly focusing on binary strings. By elucidating various algorithmic nuances overlooked in prior theoretical formulations, our solution serves as a conduit between the realms of text processing and quantum computing, fostering cross-disciplinary dialogue and innovation.
The Great Textual Hoax: Boosting Sampled String Matching with Fake Samples
12th International Conference on Fun with Algorithms (FUN 2024) • doi.org/10.4230/LIPIcs.FUN.2024.13
This paper explores character distance sampling, a cutting-edge text sampling technique focusing on sampling distances between characters in a selected alphabet. We propose the introduction of strategically placed fake samples, which significantly reduce the required index space by nearly 50% without compromising the algorithm's correctness. This method also enhances the algorithm’s efficiency under specific conditions.
Towards an Efficient Text Sampling Approach for Exact and Approximate Matching
Prague Stringology Conference 2021 • stringology.org/event/2021/p07
In this paper we present some preliminary results obtained in the attempt to extend sampled-string matching to the general case of approximate string matching. Specifically, we introduce a new sampling approach which turns out to be suitable for both exact and approximate matching and evaluate it in the context of a specific case of approximate matching, the order preserving pattern matching problem.