36 citations · 94 across the 10 of their papers we have counts for
10 papers
Technology Beats Algorithms (in Exact String Matching)
Jorma Tarhio, Jan Holub, Emanuele Giaquinta
More than 120 algorithms have been developed for exact string matching within the last 40 years. We show by experiments that the \naive{} algorithm exploiting SIMD instructions of…
Run-Length Encoded Nondeterministic KMP and Suffix Automata
Emanuele Giaquinta
We present a novel bit-parallel representation, based on the run-length encoding, of the nondeterministic KMP and suffix automata for a string with at least two distinct symbol…
Longest common substrings with k mismatches
Tomas Flouri, Emanuele Giaquinta, Kassian Kobert +1
The longest common substring with -mismatches problem is to find, given two strings and , a longest substring of and of such that the Hamming…
Alternative Algorithms for Lyndon Factorization
Sukhpal Singh Ghuman, Emanuele Giaquinta, Jorma Tarhio
We present two variations of Duval's algorithm for computing the Lyndon factorization of a word. The first algorithm is designed for the case of small alphabets and is able to skip…
On a compact encoding of the swap automaton
Kimmo Fredriksson, Emanuele Giaquinta
Given a string of length over an alphabet of size , a swapped version of is a string derived from by a series of local swaps, i.e., swaps of adjacent symbols…
Motif matching using gapped patterns
Emanuele Giaquinta, Kimmo Fredriksson, Szymon Grabowski +2
We present new algorithms for the problem of multiple string matching of gapped patterns, where a gapped pattern is a sequence of strings such that there is a gap of fixed length b…
Indexes for Jumbled Pattern Matching in Strings, Trees and Graphs
Ferdinando Cicalese, Travis Gagie, Emanuele Giaquinta +4
We consider how to index strings, trees and graphs for jumbled pattern matching when we are asked to return a match if one exists. For example, we show how, given a tree containing…
Approximate pattern matching with k-mismatches in packed text
Emanuele Giaquinta, Szymon Grabowski, Kimmo Fredriksson
Given strings of length and of length over an alphabet of size , the string matching with -mismatches problem is to find the positions of all the substrings i…
New algorithms for binary jumbled pattern matching
Emanuele Giaquinta, Szymon Grabowski
Given a pattern and a text , both strings over a binary alphabet, the binary jumbled string matching problem consists in telling whether any permutation of occurs in …
String Matching with Inversions and Translocations in Linear Average Time (Most of the Time)
Szymon Grabowski, Simone Faro, Emanuele Giaquinta
We present an efficient algorithm for finding all approximate occurrences of a given pattern of length in a text of length allowing for translocations of equal leng…