Какой алгоритм .Net использовать для поиска шаблона в строке?

Question

Сейчас я изучаю алгоритмы поиска строк и задаюсь вопросом, какой алгоритм используется для функции .NET String.Contains, например. Отражатель показывает, что эта функция используется, но я понятия не имею, что означает ее название.

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.

Answer 2

Я не смог найти эту заглушку метода, но я думаю, что это локально-специфическое свертывание регистра для поиска без учета регистра.

Answer 3

Зачем использовать отражатель, если доступен исходный код ?