Two equal length strings s and s', over alphabets Σ_s and IJSI , parameterize match if there exists a bijection π:Σ_s→Σ_s', such that π(s) = a', 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 n 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(nk~(1.5)+mk log m) time algorithm for this problem where m = |p| and n = |i|.
展开▼
机译：在字母表Σ_S和IJSI上，参数化匹配如果存在双突出π：Σ_S→Σ_s“，则为π（s）= a'，其中π（s）是每个字符的重命名通过π。近似参数化匹配是在文本字符串T的每个位置找到模式p的问题，这是最大化从p的特征映射到t的相适当的字符数。我们的主要结果是O（1.5）+ MK log m）时间算法在其中m = | p |和n = | i |。
展开▼
