String matching under a general matching relation

Muthukrishnan, S. ; Ramesh, H. (1995) String matching under a general matching relation Information and Computation, 122 (1). pp. 140-148. ISSN 0890-5401

Full text not available from this repository.

Official URL:

Related URL:


In standard string matching, each symbol matches only itself, in other string matching problems, e.g. the string matching with "don′t-cares" problem, a symbol may match several symbols. In general, an arbitrary many-to-many matching relation might hold between symbols. We consider a general string matching problem in which such a matching relation is specified and those positions in a text t, of length n, are sought at which the pattern p, of length m, matches under this relation. Depending upon the existence of a simple and easily recognizable property in the given matching relation, we show that string matching either requires linear (i.e. O (n + m)) time or is at least as hard as boolean convolution. As an application, we show that the matching relations of several independently studied string matching problems do indeed fall into the latter (hard) category. We also give a generic string matching algorithm that works for any matching relation and has complexity o (nm) except for very "large" matching relations.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
ID Code:102279
Deposited On:09 Mar 2018 11:23
Last Modified:09 Mar 2018 11:23

Repository Staff Only: item control page