With regard to your comment about complexity, the cunning thing here is that these algorithms find a substring in a string very quickly, often without even look

With regard to your comment about complexity, the cunning thing here is that these algorithms find a substring in a string very quickly, often without even looking at every character in the string. For example, Boyer-Moore (http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algor...) starts by looking at the end of the substring. If it finds a match, it searches earlier. If it does not find a match, it can skip ahead by several characters (possibly even the length of the substring, depending on how the match failed). How much to skip ahead is a bit complicated, but can be calculated in advance. Consider searching for a substring consisting of 1000 'a's. Boyer-Moore starts by looking at the 1000th (1-indexed) character. If it's an 'a', it then walks back and checks the 999th, 998th etc. However, if it's not an 'a', it can immediately skip on to examine the 2000th character, i.e. only looking at 1 in every 1000 characters. As you can imagine, this can be very fast! The Railgun implementation seems to be a combination of improved Boyer-Moore (Boyer-Moore-Horspool-Sunday) with Rabin-Karp (which uses hashing). My understanding is that these algorithms complement each other, so if you have an input string that is particularly inefficient with one algorithm, it automatically picks the other one. Since many programs have string-searching in their innermost loops, spending some time optimizing this function can be worthwhile.