Distributed Pattern Matching Using Finite Automata
J. Holub, C.S. Iliopoulos, B. Melichar, L. Mouchard · HAL (Le Centre pour la Communication Scientifique Directe) · 2001
Here we study a family of distributed pattern matching problems: we compute all the occurrences of a pattern in a text, where the pattern and/or the text can be either "singular" (ordinary) strings or "multiple" ones (strings distributed in several lines). We examine several combinations of singular and multiple text/patterns. We construct nondeterministic finite automata (NFA) for these problems and show their simulation using the Shift-Or algorithm.