Automata-based Algorithm for Multiple Word Matching
Majed AbuSafiya · International Journal of Advanced Computer Science and Applications · 2021
In this paper, an automata-based algorithm that finds the valid shifts of a given set of words W in text T is presented. Unlike known string matching algorithms, a preprocessing phase is applied to T and not to the words being searched for. In this phase, a deterministic finite state automaton (DFA) that recognizes the words in T is built and is augmented with their shifts in T. The preprocessing phase is relatively expensive in terms of time and space. However, it needs to be done once for any number of words to match in a given text document. The algorithm is analyzed for complexity, implemented and compared with an adjusted version of KMP algorithm. It showed better performance than KMP algorithm for large number of words to match in T.