[sr-dev] str_str function

Hello, str_str function searches for a substring into a bigger string. 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 Regards, Vicente.