Какой алгоритм используется для функции Pos() в Паскале?

Как название, Грубая сила, Карп-Рабин, Кнутт-Моррис-Пратт, Бойер Мур, ... или еще? И какая сложность функции Pos() в Паскале?


algorithm time-complexity pascal string-search
person phqb    schedule 22.09.2014    source источник
comment
вероятно, зависит от компилятора   -  person thang    schedule 22.09.2014
comment
Вам нужно будет указать, какой компилятор Pascal вы имеете в виду. Обычно я бы предположил грубую силу, и если вам нужен конкретный алгоритм, вам придется найти библиотеку или закодировать ее самостоятельно.   -  person LU RD    schedule 22.09.2014

Ответы (1)


arrow_upward
2
arrow_downward

В Delphi это ручной перебор ассемблера. Потенциально в D2006 и выше переделан проектом fastcode. В Turbo Pascal он тоже был написан вручную на ассемблере, но старше (вероятно, rep scasb)

В Free Pascal он использует indexbyte(), который является зависящим от архитектуры примитивом "поиск байта в блоке памяти", реализуемым сканированием по двойным словам.

IOW он просто сканирует первый равный символ, поэтому я предполагаю, что это то, что вы имеете в виду под грубой силой.

Существуют различные реализации Delphi Boyer Moore, которые можно использовать на случай, если вам нужно искать в больших текстах, но из-за их дополнительного выделения памяти они обычно плохо работают с короткими строками.

(2020-06-04 после сообщения на форуме Lazarus со ссылкой на эту тему:

Тем временем в RTL есть реализация BMH )

person Marco van de Voort    schedule 22.09.2014