c# - What algorithm .Net use for searching a pattern in a string?

Question

I'm studying string searching algorithms now and wondering what algorithm is used for .NET String.Contains function for example. Reflector shows that this function is used but I have no idea what its name means.

private static extern int InternalFindNLSStringEx(IntPtr handle, string localeName, int flags, string source, int sourceCount, int startIndex, string target, int targetCount);

Answer 1

It’s just the na?ve string search implementation via a nested loop over the text and the pattern, with O(n·m) runtime.

In particular, the MSDN doesn’t specify the performance of this method so it’s not safe to assume a better performance.

Furthermore, most advanced pattern searching methods are quite specialised for certain string types and while there are better general-purpose search algorithms, implementing one in String.IndexOf is somewhat of an unnecessary optimisation.

The reason is simple: if you require an efficient pattern search then you’ll implement your own anyway, custom-tailored to fit your particular data. So there’s no need to implement something fancy in the general-purpose library.

---

As of 2016 (with the Core CLR source code now available), the implementation is still using a na?ve nested loop. This is implemented in NewApis::IndexOfString and NewApis::FastIndexOfString, which are called (via InternalFindNLSStringEx) from the managed String.Contains and String.IndexOf functions.