### Abstract

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 text positions are sought at which the pattern matches under this relation. Depending upon the existence of a simple, easily recognizable property in the given matching relation, we show that string matching either requires time linear in the text and pattern lengths or is at least as hard as boolean multiplication. Since the existence of a linear time algorithm for boolean multiplication has been a long-standing open question, designing linear time algorithms for matching relations in the latter category appears to be hard. 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 initiate the study of a generic string matching algorithm that works for any matching relation. We give an algorithm that given any matching relation, pattern and text runs in O(n(sm)^{1/3} polylog(m)), where n and m are the sizes of the text and the pattern respectively, and s is a factor related to the size of the given matching relation. This complexity is o(nm) except for very dense matching relations.

Original language | English (US) |
---|---|

Title of host publication | Foundations of Software Technology and Theoretical Computer Science - 12th Conference, Proceedings |

Editors | Rudrapatna Shyamasundar |

Publisher | Springer Verlag |

Pages | 356-367 |

Number of pages | 12 |

ISBN (Print) | 9783540562870 |

DOIs | |

State | Published - 1992 |

Event | 12th Conference on Foundations of Software Technology and Theoretical Computer Science, 1992 - New Delhi, India Duration: Dec 18 1992 → Dec 20 1992 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 652 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 12th Conference on Foundations of Software Technology and Theoretical Computer Science, 1992 |
---|---|

Country | India |

City | New Delhi |

Period | 12/18/92 → 12/20/92 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'String matching under a general matching relation'. Together they form a unique fingerprint.

## Cite this

*Foundations of Software Technology and Theoretical Computer Science - 12th Conference, Proceedings*(pp. 356-367). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 652 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-56287-7_118