我现在正在研究字符串搜索算法,并且想知道.NET String使用哪种算法。例如包含函数。Reflector显示使用了此功能,但我不知道它的名称是什么意思。
private static extern int InternalFindNLSStringEx(IntPtr handle, string localeName, int flags, string source, int sourceCount, int startIndex, string target, int targetCount);
这只是通过在文本和模式上使用O(n·m)运行时的嵌套循环进行的简单字符串搜索实现。
特别是,MSDN没有指定此方法的性能,因此假设性能更好是不安全的。
此外,最先进的模式搜索方法是相当专业的某些字符串类型,虽然有 有 更好的通用搜索算法,在实现一个String.IndexOf有点不必要的优化。
String.IndexOf
原因很简单:如果您 需要 有效的模式搜索,那么无论如何都将实现自己的,定制的以适合您的特定数据。因此,无需在通用库中实现任何花哨的功能。
截至2016年(现已提供Core CLR源代码),该实现仍在使用幼稚的嵌套循环。这是在NewApis::IndexOfString和中实现的,并NewApis::FastIndexOfString通过InternalFindNLSStringEx被管理String.Contains和String.IndexOf函数调用(通过)。
NewApis::IndexOfString
NewApis::FastIndexOfString
InternalFindNLSStringEx
String.Contains