Какой алгоритм использование .NET для поиска шаблона в строке?
Я изучаю алгоритмы поиска строки теперь и задаюсь вопросом, какой алгоритм используется для Строки.NET. Содержит функцию, например. Отражатель показывает, что эта функция используется, но я понятия не имею, что означает ее имя.
private static extern int InternalFindNLSStringEx(IntPtr handle, string localeName, int flags, string source, int sourceCount, int startIndex, string target, int targetCount);
3 ответа
Это просто наивная реализация поиска по строке с помощью вложенного цикла по тексту и шаблону с временем выполнения O (n · m).
В частности, MSDN не указывает производительность этого метода, поэтому небезопасно предполагать лучшую производительность.
Кроме того, наиболее продвинутые методы поиска по шаблонам довольно специализированы для определенных типов строк, и хотя существуют лучшие алгоритмы поиска общего назначения, реализация одного из них в String.IndexOf в некоторой степени является ненужная оптимизация.
Причина проста: если вам требуется эффективный поиск по шаблону, вы все равно реализуете свой собственный, адаптированный к вашим конкретным данным. Так что нет необходимости реализовывать что-то необычное в универсальной библиотеке.
По состоянию на 2016 год (теперь доступен исходный код Core CLR) реализация все еще использует простой вложенный цикл. Это реализовано в NewApis :: IndexOfString и NewApis :: FastIndexOfString , которые вызываются (через InternalFindNLSStringEx ) из управляемого String.Contains ] и String.IndexOf функции.
Я не смог найти эту заглушку метода, но, как мне кажется, она учитывает локальный регистр при поиске без учета регистра.