Jorma Tarhio

Jorma Tarhio


Research Focus & Metrics

Academic Career Length

45Years (1982-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
30 April 1988 in Theoretical Computer Science
Verified
Journal Article
Closed access
JTJorma Tarhio
Jorma Tarhio
EUEsko Ukkonen
Esko Ukkonen

1 April 1993 in SIAM Journal on Computing
Verified
Journal Article
Closed access
JTJorma Tarhio
Jorma Tarhio
EUEsko Ukkonen
Esko Ukkonen
The Boyer–Moore idea applied in exact string matching is generalized to approximate string matching. Two versions of the problem are considered. The k mismatches problem is to find all approximate occurrences of a pattern string (length m) in a text string (length n) with at most k mismatches. The generalized Boyer–Moore algorithm is shown (under a mild independence assumption) to solve the problem in expected time $O(kn({1 / {(m - k) + ({k / c})}}))$, where c is the size of the alphabet. A related algorithm is developed for the k differences problem, where the task is to find all approximate occurrences of a pattern in a text with $ \leqslant k$ differences (insertions, deletions, changes). Experimental evaluation of the algorithms is reported, showing that the new algorithms are often significantly faster than the old ones. Both algorithms are functionally equivalent with the Horspool version of the Boyer–Moore algorithm when $k = 0$.

1 January 1995
Verified
Book Chapter
Closed access
PDF file
ESErkki Sutinen
Erkki Sutinen
JTJorma Tarhio
Jorma Tarhio

1 January 2003
Verified
Book Chapter
Closed access
PDF file
HPHannu Peltola
Hannu Peltola
JTJorma Tarhio
Jorma Tarhio

1 January 2010
Verified
Book Chapter
Closed access
PDF file
BĎBranislav Ďurian
Branislav Ďurian
HPHannu Peltola
Hannu Peltola
LSLeena Salmela
Leena Salmela
JTJorma Tarhio
Jorma Tarhio

1 January 2010 in Information Processing Letters
Verified
Journal Article
Closed access
BĎBranislav Ďurian
Branislav Ďurian
JHJan Holub
Jan Holub
HPHannu Peltola
Hannu Peltola
JTJorma Tarhio
Jorma Tarhio