Had a peek at the strstr implementation in glibc. Not sure what algorithm it uses though the author claims its the fastest (does it beat KMP,Boyer-Moore ?) Also, glibc has some assembly language versions of string functions which are supposedly used when you compile with -O1 upwards. I should try to get some zen with objdump to see if I can figure out if the assembly versions get used in x86 or not