C ++ string :: find сложность
Почему в C ++ реализована string :: find () не используется алгоритм KMP (и не выполняется в O (N + M) ), а выполняется в O (N * M) ? Это исправлено в C ++ 0x?
Если сложность текущего поиска не равна O (N * M) , что это такое?
, тогда какой алгоритм реализован в gcc? это КМП? если нет, то почему?
Я проверил это, и время работы показывает, что он выполняется в O (N * M)
1 ответ
Если Вы собираетесь быть поиском того же шаблона в нескольких текстах. Алгоритм BoyerMoore является хорошим выбором, потому что таблицы шаблона должны только быть вычисленными однажды, но используются многократно при поиске нескольких текстов. Если Вы только собираетесь искать шаблон однажды в 1 тексте, хотя, издержки вычислений таблиц наряду с издержками выделения памяти замедляют Вас слишком много и станд.:: string.find (....) изобьет Вас, так как он не выделяет памяти и не имеет никаких издержек. Повышение имеет несколько алгоритмов поиска строки. Я нашел, что BM был порядком величины медленнее в случае единственного поиска шаблона в 1 тексте, чем станд.:: string.find (). Для моих случаев BoyerMoore был редко быстрее, чем станд.:: string.find (), ища несколько текстов с тем же шаблоном. Вот ссылка на BoyerMoore BoyerMoore