Какова стоимость / сложность вызова функции String.indexof ()

Question

Какова стоимость / сложность вызова функции String.indexof ()

Answer 1

IIRC Реализация Java .indexOf() - это просто алгоритм наивного сопоставления строк , который является O(n+m) средним и O(n*m) наихудшим случаем.

На практике это достаточно быстро;Я проверил его на сравнительно больших игольных (> 500 символов) и стогах сена (несколько МБ), и он сделал бы сопоставление менее чем за секунду (в среднем домашнем компьютере).Имейте в виду, я заставил его пройти через весь стог сена.

Answer 2

Зависит от реализации.

Например, при поиске строки в более длинной строке «Алгоритм Turbo Boyer-Moore требует дополнительного постоянного пространства для завершения поиска в 2n сравнениях (в отличие от 3n для Бойера-Мура), где n это количество символов в тексте для поиска. " (см. Википедия ).

Answer 3

В java, если вызов - string1.indexOf (string2), затраты времени будут O (m - n), где m - длина строки1, а n - длина строки 2.