Parameterized searching with mismatches for run-length encoded strings

Parameterized matching between two strings occurs when it is possible to reduce the first one to the second by a renaming of the alphabet symbols. We present an algorithm for searching for parameterized occurrences of a patten in a textstring when both are given in run-length encoded form. The proposed method extends to alphabets of arbitrary yet constant size with O (vertical bar r(p)vertical bar x vertical bar r(t)vertical bar) time bounds, previously achieved only with binary alphabets. Here r(p) and r(t) denote the number of runs in the corresponding encodings for p and t. For general alphabets, the time bound obtained by the present method exhibits a polynomial dependency on the alphabet size. Such a performance is better than applying convolution to the cleartext, but leaves the problem still open of designing an alphabet independent O (vertical bar r(p)vertical bar x vertical bar r(t)vertical bar) time algorithm for this problem. (C) 2012 Elsevier B.V. All rights reserved.