The IRMA Community
Newsletters
Research IRM
Click a keyword to search titles using our InfoSci-OnDemand powered search:
|
A New Algorithm for Subset Matching Problem Based on Set-String Transformation
Abstract
In computer engineering, a number of programming tasks involve a special problem, the so-called tree matching problem (Cole & Hariharan, 1997), as a crucial step, such as the design of interpreters for nonprocedural programming languages, automatic implementation of abstract data types, code optimization in compilers, symbolic computation, context searching in structure editors and automatic theorem proving. Recently, it has been shown that this problem can be transformed in linear time to another problem, the so called subset matching problem (Cole & Hariharan, 2002, 2003), which is to find all occurrences of a pattern string p of length m in a text string t of length n, where each pattern and text position is a set of characters drawn from some alphabet S. The pattern is said to occur at text position i if the set p[j] is a subset of the set t[i + j - 1], for all j (1 = j = m). This is a generalization of the ordinary string matching and is of interest since an efficient algorithm for this problem implies an efficient solution to the tree matching problem. In addition, as shown in (Indyk, 1997), this problem can also be used to solve general string matching and counting matching (Muthukrishan, 1997; Muthukrishan & Palem, 1994), and enables us to design efficient algorithms for several geometric pattern matching problems. In this article, we propose a new algorithm on this issue, which needs only O(n + m) time in the case that the size of S is small and O(n + m·n0.5) time on average in general cases.
Related Content
|
Tereza Raquel Merlo, Nayana Madali M. Pampapura, Jason M. Merlo.
© 2024.
14 pages.
|
|
Kris Swen Helge.
© 2024.
9 pages.
|
|
Ahmad Tasnim Siddiqui, Gulshaira Banu Jahangeer, Amjath Fareeth Basha.
© 2024.
12 pages.
|
|
Jennie Lee Khun.
© 2024.
19 pages.
|
|
Tereza Raquel Merlo.
© 2024.
19 pages.
|
|
Akash Bag, Paridhi Sharma, Pranjal Khare, Souvik Roy.
© 2024.
31 pages.
|
|
Akash Bag, Upasana Khattri, Aditya Agrawal, Souvik Roy.
© 2024.
28 pages.
|
|
|