String Search. The Boyer Moore algorithm
Posted: Sun Jul 26, 2026 10:23 am
More Fun with Flowcode 
Reading a copy of Niklaus Wirth's 'Algorithms + Data Structures' (from 1980s) - I came across the Boyer Moore algorithm...
A common problem in programming is searching a string (or array of bytes) looking for a match with a pattern. Think genetic sequencing?
The normal string search uses a 'linear' algorithm - and for searching large data arrays with complex strings there are better algorithms.
Here I use the Boyer Moore algorithm. I used an Arduino - and because of the limited RAM I allow data in the range 0..127 (printable ASCII) and strings. In the real world - this would be 0..255 (or possiby not for genetic data?)
The BoyerMoore algorithm works best with longer patterns - and here is a rather contrived example - in a string of 1500 random characters - I copy some instances (here 3 and no check that they don't overlap) of the pattern - then time 1000 searches for (all) occurrences of the pattern in the data string.
Obviously - searching for the same data 1000 times is unrealistic - and I could optimise for this by only doing the setup once (BadChar) - but that might be construed as cheating? However this could be done for searching for the same data in multiple data arrays.
Here it is ~twice as fast as the linear search (3792ms linear and 1739ms BM for 1000 iterations),
Martin
Reading a copy of Niklaus Wirth's 'Algorithms + Data Structures' (from 1980s) - I came across the Boyer Moore algorithm...
A common problem in programming is searching a string (or array of bytes) looking for a match with a pattern. Think genetic sequencing?
The normal string search uses a 'linear' algorithm - and for searching large data arrays with complex strings there are better algorithms.
Here I use the Boyer Moore algorithm. I used an Arduino - and because of the limited RAM I allow data in the range 0..127 (printable ASCII) and strings. In the real world - this would be 0..255 (or possiby not for genetic data?)
The BoyerMoore algorithm works best with longer patterns - and here is a rather contrived example - in a string of 1500 random characters - I copy some instances (here 3 and no check that they don't overlap) of the pattern - then time 1000 searches for (all) occurrences of the pattern in the data string.
Obviously - searching for the same data 1000 times is unrealistic - and I could optimise for this by only doing the setup once (BadChar) - but that might be construed as cheating? However this could be done for searching for the same data in multiple data arrays.
Here it is ~twice as fast as the linear search (3792ms linear and 1739ms BM for 1000 iterations),
Martin