Automata play a very important role in the design of string matching algorithms as their use has always led to elegant and very efficient solutions in practice. In this paper, we present a new general approach to the exact string matching algorithm based on a non-standard efficient simulation of the suffix automaton of the pattern and give a specific efficient implementation of it. To show the effectiveness of our algorithm, we perform an extensive comparison against the most effective alternatives known in literature in terms of search speed and shift advancements. From our experimental results the new algorithm turns out to be very efficient in practical cases scaling much better when the length of the pattern increases, improving the search speed by nearly 10 times under suitable conditions.
Efficient String Matching Based on a Two-Step Simulation of the Suffix Automaton
Faro S.;Scafiti S.
2021-01-01
Abstract
Automata play a very important role in the design of string matching algorithms as their use has always led to elegant and very efficient solutions in practice. In this paper, we present a new general approach to the exact string matching algorithm based on a non-standard efficient simulation of the suffix automaton of the pattern and give a specific efficient implementation of it. To show the effectiveness of our algorithm, we perform an extensive comparison against the most effective alternatives known in literature in terms of search speed and shift advancements. From our experimental results the new algorithm turns out to be very efficient in practical cases scaling much better when the length of the pattern increases, improving the search speed by nearly 10 times under suitable conditions.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
