Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
One naive approach in solving multiple pattern matching problem is to call single pattern matching procedure on each of the pattern.
There must be some drawbacks in this approach, given the variety of multiple pattern matching algorithms such as Aho Cornsick algorithm, which prove to be more efficient.
So what are the drawbacks on this straightforward yet naive approach? In what scenario is this algorithm doing unnecessary works?
One common way of solving pattern matching problems is compiling a DFA that matches the pattern. If you have several patterns in mind, you can combine all of them into a single DFA, which will match all of them with a single pass, rather than one pass per pattern. On the flip side, the DFA could have many states and so might not fit into cache, which would cause a performance hit.
A simple case in which repeated pattern matching is inefficient would be if some patterns are prefixes of others. Many of the standard algorithms can efficiently report occurrences of a prefix of a pattern at no additional cost.
