什么算法.Net用于搜索字符串中的模式？

Question

我现在正在研究字符串搜索算法,并想知道.NET String.Contains函数用于什么算法.Reflector显示使用了这个函数,但我不知道它的名字是什么意思.

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

Answer 1

它只是通过文本和模式的嵌套循环实现的天真字符串搜索实现,具有O(n·m)运行时.

特别是,MSDN没有指定此方法的性能,因此假设更好的性能是不安全的.

此外,最先进的模式搜索方法是比较专业的某些字符串类型,虽然有有更好的通用搜索算法,实现一个以String.IndexOf在一定程度上不必要的优化.

原因很简单:如果您需要有效的模式搜索,那么无论如何您都将实现自己的,自定义以适合您的特定数据.所以没有必要在通用库中实现一些奇特的东西.

截至2016年(现在可以使用Core CLR源代码),实现仍然使用一个简单的嵌套循环.这是在NewApis::IndexOfString和中实现的NewApis::FastIndexOfString,InternalFindNLSStringEx从托管String.Contains和String.IndexOf函数调用(via ).