An efficient pattern matching algorithm on a subclass of context free grammars

Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)


There is a close relationship between formal language theory and data compression. Since 1990's various types of grammar-based text compression algorithms have been introduced. Given an input string, a grammar-based text compression algorithm constructs a context-free grammar that only generates the string. An interesting and challenging problem is pattern matching on context-free grammars P of size m and T of size n, which are the descriptions of pattern string P of length M and text string T of length N, respectively. The goal is to solve the problem in time proportional only to m and n, not to M nor N. Kieffer et al. introduced a very practical grammar-based compression method called multilevel pattern matching code (MPM code). In this paper, we propose an efficient pattern matching algorithm which, given two MPM grammars P and T, performs in O(mn2) time with O(mn) space. Our algorithm outperforms the previous best one by Miyazaki et al. which requires O(m2n 2) time and O(mn) space.

Original languageEnglish
Pages (from-to)225-236
Number of pages12
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publication statusPublished - 2004

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'An efficient pattern matching algorithm on a subclass of context free grammars'. Together they form a unique fingerprint.

Cite this