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

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


algorithm time-complexity pascal string-search
person phqb    schedule 22.09.2014    source източник
comment
вероятно зависи от компилатора   -  person thang    schedule 22.09.2014
comment
Ще трябва да посочите кой паскал компилатор имате предвид. Като цяло бих предположил груба сила и ако искате конкретен алгоритъм, ще трябва да намерите библиотека или да го кодирате сами.   -  person LU RD    schedule 22.09.2014

Отговори (1)


arrow_upward
2
arrow_downward

В Delphi това е ръчно кодирана груба сила на асемблер. Потенциално в D2006 и по-нови, преработени от проект за бързо кодиране. В Turbo Pascal също беше ръчно кодиран асемблер, но по-стар (вероятно rep scasb)

На Free Pascal той използва indexbyte(), който е зависим от архитектурата примитивен „търсен байт в блок от паметта“, реализиран от dword wise сканиране.

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

Има различни реализации на Delphi Boyer Moore, които могат да се използват, в случай че трябва да търсите в по-големи текстове, но поради допълнителното им разпределение на паметта те обикновено дават лош резултат при къси низове.

(2020-06-04 след публикация във форума на Lazarus, препращаща към тази тема:

Междувременно има BMH внедряване в RTL )

person Marco van de Voort    schedule 22.09.2014