Approximate Parameterized Matching

Two equal length strings s and s′, over alphabets Σ _s and Σ _s′, parameterize match if there exists a bijection π:Σ _s → Σ _s′, such that π (s)=s′, where π (s) is the renaming of each character of s via π. Approximate parameterized matching is the problem of finding for a pattern p, at each location of a text string t, a bijection π that maximizes the number of characters that are mapped from p to the appropriate |p|-length substring of t.Our main result is an O(nk1.5+mklog m) time algorithm for this problem where m=|p| and n = |t|.