Алгоритм поиска подстроки....

[MadFish]

Собстственно нужен алгоритм поиска подстроки. Основное ограничение- скорость!!! Пока остановился на ДКА(детерменированный конечный автомат), но может что-нибудь получше есть?

[RomanPshenichny]

Тебе надо искать строчку внутри строки или таки регулярное выражение внутри строки?

[SeQuick]

Функция InStr

Возвращает значения типа Variant

Синтаксис:

InStr([start, ]string1, string2[, compare])

Аргументы функции:

Start: Необязательный (Числовое выражение, задающее положение с которого начинается каждый поиск). Если этот аргумент опущен, начинается поиск с начала строки. Если Start имеет значение Null тогда возникает ошибка Указание аргумента Start является обязательным если указан аргумент Compare.

String1 : Обязательный. Строковое выражение, в котором выполняется поиск.

String2 : Обязательный. Искомое строковое выражение

Compare : Необязательный. Указывает способ сравнения строк. Этот аргумент можен быть опущен или иметь значение 0, 1 или 2. Если следует указать двоичное сравнение, стоит указать 0 (используется по умолчанию) Что бы выполнить посимвольное сравнение без учёта регистра, следует указать 1. Только в Microsoft Access допускается использование значения 2 для выполнения сравнения на основании сведений, содержащихся в базе данных. Если Аргумен имеет значение Null, возникает ошибка. Если аргумент Compare опущен, способ сравнения строк определяется значением параметра инструкции Option Compare.

[Gendalf]

Сообщение от MadFish

Собстственно нужен алгоритм поиска подстроки. Основное ограничение- скорость!!! Пока остановился на ДКА(детерменированный конечный автомат), но может что-нибудь получше есть?

Может стоит почитать на тему, как это реализовано в БД? Этот вопрос кажется обсуждался здесь.

[MadFish]

to SeQuick:
Спасибо за ответ, но я просил подсказать мне именно алгоритм, а не описание какой-то функции...
to Gendalf
буду крайне признателен если кинешь в меня ссылкой, а то пока ничего путного не нашел
to RomanPshenichny:
Мне нужно найти подстроку в строке (точное совпадение а не поиск по регекспу) .

[SeQuick]

Перебираются попорядку все символы строки
Цикл FOR i=0 TO Len(String as string (твоя строка))


Ищем первую букву нужного нам в поиске слова(то что мы ищем)
Например надо найти "abc" в abcdef

Dim i as integer ' объявляем переменную-счётчик

For i=1 TO len(abcdef) ' перебираем посимвольно все символы введённой строки

If left(abcdef, 1) (первый символ строки) = left (abc, 1)(первый символ искомой строки) then ' если да, то

If mid(abcdef, i + 1, 1) = mid (abc, 2, 1) then 'проверяем Идёт ли за первым символом второй из искомой строки

if left(abcdef, 1+2 , 1) = right(abc, 1) then ' если следом за вторым следует третий символ искомой строки тогда

msgbox "Строка найдена"

else
i = i + 1 ' идём на следующий символ
end if

else
i = i + 1 ' идём дальше
end if
else

i = i + 1 ' и на следующий символ
end if
Ну вот приблизительно в ломтиках кода я описал Принцип действия поиска кода по строке. Сам не проверял этот код, думаю ты поймёшь что надо для этого! :

Использованные функции:

Left (строка или строковая переменная, количество букв (целое) ) -- возвращает n-ное количество первых букв строки

Mid (строка или строковая переменная, начальная позиция откуда отсчитывать, количество символов (целое), сколько нужно отсчитать от данной позиции в строке) -- Короче функция для выдирания куска строки. Возвращает строку.

Right (строка или строковая переменная, количество букв (целое) n) -- возвращает n-ное количество последних букв строки)

[Ant0]

For i=1 TO len(abcdef) ' перебираем посимвольно все символы введённой строки

уже не оптимально! на каждой итерации вычесляеться сколько символов в строке - ресурсы....

[aerin]

SeQuick
MadFish написал в своем первом посте, что

Пока остановился на ДКА(детерменированный конечный автомат)

т.е. человек как минимум знаком с теоретическими основами, вы же в своих ответах демонстрируете полнейшее незнание предмета. Дело в том, что оценка эффективности алгоритмов - это не гадание на кофейной гуще, а точная наука. Критерием выбора метода для данного конкретного случая является

Основное ограничение- скорость!!!

, т.е. например, алгоритм Карпа-Рабина в данном случае не подойдет, т.к. он, не требуя дополнительной памяти и предварительной обработки, в худшем случае даст время поиска O(n*m), а упомянутый автором ДКА - O(n). Но, как мне кажется, вам это пока бестолку объяснять...

[Handle]

aerin если не сложно в двух словах про алгоритм Карпа-Рабина. Очень интересно.

[SeQuick]

Сообщение от Ant0

уже не оптимально! на каждой итерации вычесляеться сколько символов в строке - ресурсы....

Я объяснил человеку на самом простом примере! Что бы ОН ПОНЯЛ. Если все такие продвинутые программеры, то почему же я ещё ни одного нормального ответа не вижу?

[maximn]

SeQuick, большое спасибо, своим алгоритмом ты просто спас меня! благодаря тебе, первая часть моей программы готова - осталась вторая. очень надеюсь, что ты и это знаешь - иначе я просто пропал. задача такая: нужно написать в окошке загадочное заклинание "Hello World!", ты не в курсе как это реализовать?

[aerin]

Handle вот первая ссылка google:
http://algolist.manual.ru/search/esearch/karp_rab.php
всяко лучше меня объяснят
тут даже сишная реализация есть.

[Handle]

Спасибо aerin. Оказывается все достаточно просто.

[aerin]

Handle кстати, посмотрел эту ссылку
http://algolist.manual.ru/search/esearch/
тут описано 15 алгоритмов, я, например, слышал далеко не о всех

[Gendalf]

Сообщение от aerin

Handle кстати, посмотрел эту ссылку
http://algolist.manual.ru/search/esearch/
тут описано 15 алгоритмов, я, например, слышал далеко не о всех

Хороший сайт! Как мне его не хватало на 1-м курсе ПММ.

Хотя тогда я активно пользовался книгой Д. Кнут (3-х томник)

[MadFish]

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

[aerin]

MadFish
Вообще-то, это не совсем моя специализация
Худший случай алгоритма Карпа-Рабина на пальцах - это случай постоянного совпадения хешей и следующего за этим тупого побайтного сравнения, т.е. алгоритм вырождается в способ SeQuick-а, плюс накладные расходы по вычислению и сравнению хеш-кодов.
По поводу ДКА. Никто ж не заставляет тебя строить полное дерево. Или заставляет?
В любом случае, imho, нужно плясать от конкретной задачи: посмотри может у твоих строк есть какая-либо особенность, которая может существенно сократить вычисления, или быть может можно произвести некий парсинг еще на этапе ввода. Т.е. сократить объем рассматриваемых данных. Когда это будет сделано, выбрать наиболее привлекательный алгоритм и доработать напильником под себя. Не зная задачи, большего тебе наверное никто не скажет.
Если задача достаточно общая, т.е. нельзя заложиться на особенности данных, то может имеет смысл посмотреть библиотеки регулярных выражений, благо в сети этого GNU-того дела навалом.

[aerin]

Запостил, а потом прочитал, что регекспы тебе не подходят...
Тогда последний абзац предыдущего поста меняем, на "И тестить. Слепить тестовый пример и запустить поиск, подсунув в качестве словаря какой-нибудь текстовый файл, замерить время."

[netwind]

дада, а то еще окажется, что сишная ф-ция strstr уделает все алгоритмы, так как писана с применением специальных команд процессора

[netwind]

дада, а то еще окажется, что сишная ф-ция strstr уделает все алгоритмы, так как писана с применением специальных команд процессора

[Balrog]

netwind "специальные команды" - это repne scasb или rep cmpsb?

Ну так если "важна скорость" - авось он не на VB решать будет. Но в общем правильный вопрос - есть ли особенности данных.

[netwind]

Balrog, ага. комбинация из scasdw и scassb наверное даже(за точность названий не ручаюсь)
а что, не уделает на современных П4 ?
в предположении что данные простые строки и компилятор не в состоянии так круто оптимизировать код

[netwind]

а ведь сканировать по 4 байта scasdw глупая идея...

[MadFish]

aerin:

Сообщение от aerin

По поводу ДКА. Никто ж не заставляет тебя строить полное дерево. Или заставляет?

Вот оно самое!!! Ты гений!!! Спасибо!!! Кажется, я слишком заработался и мне пора в отпуск. Ведь мне нужен автомат для распознавания только ОДНОЙ !!! входной строки и соответственно всеми другими состояниями можно пренебречь и переводить автомат в начальное состояние, а это на порядки уменьшает таблицу, и соответственно время на ее построение. Все летает. Еще раз спасибо всем. Тема закрыта.