|
to aerin:
Большое спасибо тебе за поддержку... Насколько я могу судить, ты тут пока единственный, кто вменяемо может ответить на мой вопрос, так что позволь обратится прямо к тебе. Eстественно, перед тем как спросить в форуме я полазил в инете и почитал книги, и честно говоря, и хотел услышать сравнительную характеристику алгоритмов Карпа-Рабина и построения ДКА. Дело в том что во-первых, мне не совсем понятно, откуда в алгоритме Карпа-Рабина взялась оценка для худшего случая - n*m, а во-вторых, меня смущает построение ДКА. При достаточно больших строках для поиска (как раз что и происходит в моем случае) построение таблицы переходов состояний для ДКА может занять значительное время. Не будет ли в таком случае алгоритм Карпа-Рабина (или возможно какая-нибудь его модификация) более предпочтительной?
|