| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 431116 | Journal of Discrete Algorithms | 2008 | 12 Pages |
Abstract
Two strings parameterize match if there is a bijection defined on the alphabet that transforms the first string character by character into the second string. The problem of finding all parameterized matches of a pattern in a text has been studied in both one and two dimensions but the research has been centered on developing algorithms with good worst-case performance. We present algorithms that solve this problem in sublinear time on average for moderately repetitive patterns.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Leena Salmela, Jorma Tarhio,