On the linear number of matching substrings

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


We study the number of matching substrings in the pattern matching problem. In general, there can be a quadratic number of matching substrings in the size of a given text. The linearizing restriction enables to find at most a linear number of matching substrings. We first explore two well-known linearizing restriction rules, the longest-match rule and the shortest-match substring search rule, and show that both rules give the same result when a pattern is an infix-free set even though they have different semantics. Then, we introduce a new linearizing restriction, the leftmost non-overlapping match rule that is suitable for find-and-replace operations in text searching, and propose an efficient algorithm for the new rule when a pattern is described by a regular expression. We also examine the problem of obtaining the maximal number of non-overlapping matching substrings.

Original languageEnglish
Pages (from-to)715-728
Number of pages14
JournalJournal of Universal Computer Science
Issue number5
Publication statusPublished - 2010

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'On the linear number of matching substrings'. Together they form a unique fingerprint.

Cite this