Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
inline proc findAll(needle: string, region: range(?) = 1:byteIndex..): []
find all occurrences of needle in string.
return type :- integer array containing starting indices of matched pattern. (1-based indexing)
empty array if no index found
Algorithm :- boyle bad character shift array with boyle moore horspool algorithm.
preprocessing phase is O(m+k) time and
O(k) space complexity
where m = length of pattern ,
n = length of string
k = numchar = 256
worst-case performance O(mn),
average time is O(n)
best case = sub-linear
use List;
var numchar = 256 : int;
var res:list(byteIndex);
var rlow:byteIndex;
var rhigh:byteIndex;
//handle region
if(!(region.hasLowBound())) then rlow = 1; else rlow=region.low;
if(!(region.hasHighBound())) then rhigh = this.len; else rhigh=region.high;
var nlen = needle.len;
//handle corner cases
if((nlen>(rhigh-rlow+1)) || (nlen==0) || (this.len==0)){
var x = res.toArray();
var finres:[0..res.size-1] int;
finres = x.reindex(0..#x.size):int;
return finres;
//preprocess the needle
//preprocess BoyleMoore bad character shift.
//preBmBs(needle ,rlow, rhigh, bmbc);
// boyle moore bad character array to store the preprocess of the input needle
var bmbc:[1..numchar] int;
for i in 1..numchar
for i in 1..(nlen-1)
//find all occurrences using BMH search
//var i = rlow;
var j = rlow;
var c = this[j+nlen-1] : byteIndex;
if(needle[nlen]==c && !(needle == this[j..j+nlen])){
j += bmbc[c];
var x = res.toArray();
var finres: [0..res.size-1] int;
finres = x.reindex(0..#x.size):int;
return finres;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment