Name
Abstract | ||
|---|---|---|
In this paper we have presented new algorithms to handle the pattern matching problem where the pattern can contain variable length gaps. Given a pattern P with variable length gaps and a text T our algorithm works in O(n + m + α log(max$_{\rm 1bi–ai))) time where n is the length of the text, m is the summation of the lengths of the component subpatterns, α is the total number of occurrences of the component subpatterns in the text and ai and bi are, respectively, the minimum and maximum number of don’t cares allowed between the ith and (i+1)st component of the pattern. We also present another algorithm which, given a suffix array of the text, can report whether P occurs in T in O(m + α loglogn) time. Both the algorithms record information to report all the occurrences of P in T. Furthermore, the techniques used in our algorithms are shown to be useful in many other contexts. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11809678_17 | COCOON |
Keywords | Field | DocType |
st component,variable length gap,total number,algorithm work,component subpatterns,suffix array,new algorithm,maximum number,algorithms record information,pattern p,pattern matching | Discrete mathematics,Combinatorics,Suffix,Suffix array,Pattern matching,Mathematics | Conference |
Volume | ISSN | ISBN |
4112 | 0302-9743 | 3-540-36925-2 |
Citations | PageRank | References |
26 | 1.10 | 15 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| M. Sohel Rahman | 1 | 488 | 56.99 |
| Costas S. Iliopoulos | 2 | 1534 | 167.43 |
| Inbok Lee | 3 | 58 | 10.49 |
| Manal Mohamed | 4 | 102 | 12.62 |
| William F. Smyth | 5 | 290 | 19.17 |