Augmenting the aho-corasick pattern matching machine

Abstract

The Aho-Corasick algorithm is a well-known method of determining the occurrences of one of several given pattern strings in a given text string. We address the question of augmenting the pattern matching machine constructed by this algorithm with a new pattern string, both on-line and off-line. We show that augmenting a machine of N nodes with a new pattern string of length m takes Θ(mN) time on-line and Θ(N) time off-line.

Keywords:

• Multiple pattern matching
• incremental updating

^∗Research partially supported by NSF grant No NCR 8706350

^∗Research partially supported by NSF grant No NCR 8706350

Notes

^∗Research partially supported by NSF grant No NCR 8706350