δγ - Parameterized Matching

被引：0
|
作者：
Lee, Inbok [1 ]
Mendivelso, Juan [2 ]
Pinzon, Yoan J. [2 ]
机构：
[1] Hankuk Aviat Univ, Sch Elect Telecommun & Comp Engn, Koyang City, Kyonggi Do, South Korea
[2] Univ Nacl Colombia, Dept Syst & Ind Engn, Res Grp Algorithms & Combinatorics ALGOS UN, Bogota, Colombia
来源：
STRING PROCESSING AND INFORMATION RETRIEVAL, PROCEEDINGS | 2008年 / 5280卷
关键词：
combinatorial algorithms; delta-matching; delta gamma-matching; parameterized matching; bipartite matching;
D O I：
暂无
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
This paper defines a new pattern matching problem by combining two paradigms: delta gamma-matching and parameterized matching. The solution is essentially obtained by a combination of bitparallel techniques and a reductions to a graph matching problem. The time complexity of the algorithm is O(nm), assuming text size n, pattern size m and a constant size alphabet.
引用
收藏
页码：236 / +
页数：4
相关论文
共 50 条
  • [1] Approximate parameterized matching
    Hazay, C
    Lewenstein, M
    Sokol, D
    ALGORITHMS ESA 2004, PROCEEDINGS, 2004, 3221 : 414 - 425
  • [2] Parameterized matching with mismatches
    Apostolico, Alberto
    Erdos, Peter L.
    Lewenstein, Moshe
    JOURNAL OF DISCRETE ALGORITHMS, 2007, 5 (01) : 135 - 140
  • [3] Approximate Parameterized Matching
    Hazay, Carmit
    Lewenstein, Moshe
    Sokol, Dina
    ACM TRANSACTIONS ON ALGORITHMS, 2007, 3 (03)
  • [4] Secure parameterized pattern matching
    Zarezadeh, Maryam
    Mala, Hamid
    Ladani, Behrouz Tork
    INFORMATION SCIENCES, 2020, 522 : 299 - 316
  • [5] Homing by parameterized scene matching
    Franz, MO
    Scholkopf, B
    Bulthoff, HH
    FOURTH EUROPEAN CONFERENCE ON ARTIFICIAL LIFE, 1997, : 236 - 245
  • [6] Parameterized inapproximability of Morse matching
    Bauer, Ulrich
    Rathod, Abhishek
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2025, 126
  • [7] Parameterized Matching: Solutions and Extensions
    Mendivelso, Juan
    Pinzon, Yoan
    PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2015, 2015, : 118 - 131
  • [8] On Counting Parameterized Matching and Packing
    Liu, Yunlong
    Wang, Jianxin
    FRONTIERS IN ALGORITHMICS, FAW 2016, 2016, 9711 : 125 - 134
  • [9] ALPHABET DEPENDENCE IN PARAMETERIZED MATCHING
    AMIR, A
    FARACH, M
    MUTHUKRISHNAN, S
    INFORMATION PROCESSING LETTERS, 1994, 49 (03) : 111 - 115
  • [10] Compressed Parameterized Pattern Matching
    Beal, Richard
    Adjeroh, Donald A.
    2013 DATA COMPRESSION CONFERENCE (DCC), 2013, : 461 - 470
12345