Am Dienstag, 12. Juni 2012, 13:05:18 schrieb Vicente Hernando: > str_str function in lib/cds/sstr.c file has a comment: /* FIXME: > reimplement using better algorithm */ > > Attached patch reimplements that function using > Boyer-Moore-Horspool-Raita algorithm, which is the one most text editors > use to search for substrings. > > Boyer-Moore-Horspool-Raita algorithm is a simplification from > Boyer-Moore one, with less preprocessing overhead. > > > If n is the string length, and m is substring length, naive brute force > algorithm has a cost of O(n*m). > > Raita algoritm has same cost in worst case but Ω(n/m) a better average > cost. > As a drawback it adds a preprocessing cost of O(m + charset_length) > where charset_length is 256 for us, because we use char. > > > Another way to approach this substring search issue would be separate it > into two functions, a preprocessing one, and a searching one. Then in > module initializacion where the function is used, calculate the needed > preprocess and when the function is called do the search only. > > > This Raita algorithm could also be useful for str_search function in > ut.c. Its usefulness depends on n, and m lengths, the bigger they are > the better the algoritm works. > > http://en.wikipedia.org/wiki/String_searching_algorithm > http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm > http://www-igm.univ-mlv.fr/~lecroq/string/node22.html
Hallo Vincente, thanks for your patch. One question, would it not make sense to use the strstr function of <string.h>, with a small wrapper, which is probably quite optimised instead of implementing it our self? Best regards, Henning _______________________________________________ sr-dev mailing list [email protected] http://lists.sip-router.org/cgi-bin/mailman/listinfo/sr-dev
