Edit page

Naive algorithm

The naive approach to the string matching problem is walking through the source starting from the beginning and checking at each position if the resulting substring equals the query pattern. While being inefficient, it may be beneficial to use it in cases where the speed advantage of another algorithm is neglegible or does not outhweigh the additional setup needed (for example if your source and query pattern are really short). (Source: Wikipedia)

Complexity

NamePreprocessingAverageWorstSpaceComments
Naive algorithmnonen*mm*(n-m+1)none

* Where n = length of the source; m = length of the query pattern; k = size of the Alphabet

References

  • Geeksforgeeks
  • Wikipedia
  • YouTube