Paper Info
Title
New Variants of Pattern Matching with Constants and Variables.
Abstract
Given a text and a pattern over two types of symbols called constants and variables, the parameterized pattern matching problem is to find all occurrences of substrings of the text that the pattern matches by substituting a variable in the text for each variable in the pattern, where the substitution should be injective. The function matching problem is a variant of it that lifts the injection constraint. In this paper, we discuss variants of those problems, where one can substitute a constant or a variable for each variable of the pattern. We give two kinds of algorithms for both problems, a convolution-based method and an extended KMP-based method, and analyze their complexity.
Year
DOI
Venue
2018
10.1007/978-3-319-73117-9_43
Lecture Notes in Computer Science
Keywords
DocType
Volume
Pattern matching,Parameterized pattern matching,Function matching,Parameterized pattern queries
Conference
10706
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
5
4
Name
Order
Citations
PageRank
Yuki Igarashi1638.72
Diptarama241.85
Ryo Yoshinaka317226.19
Ayumi Shinohara493688.28