Версия для печати темы

Автор: Серг 5.02.2004 19:36

Здравствуйте!
Есть текст и есть слова. Так вот в тексте нужно найти строку и символ, где впервые попадается любое из слов.
Так вот вопрос в том, как можно произвести поиск!
Я делал так: брал слово и получал его "код" - for i:=1 to length(s) do codes[i]:=codes[i]+ord[s]; и проходил полностью весь текст.
Проблема в том, что если слово другое, но одинаковые буквы в нем, пример: drea и read.
А целиком слово я хранить не могу, т.к. общее количество слов достигает 1000, да притом все делается на Паскале.

Ограничения такие: максимальное число слов: 1000. Текст 400Кб

Как можно еще попробовать ?

Автор: trminator 5.02.2004 20:45

Можно попробовать выбрать другой "код". То, что ты сделал, называется хэшированием (или хешированием) - слову сопоставляется число. Нужно подобрать хэш (хеш?)-функцию так, чтобы не было совпадений . То есть не складывать коды букв, а что-нибудь этакое замутить... ну... (вертит пальцами в воздухе +) )

Автор: UtaH 6.02.2004 9:26

А если попробовать складывать коды букв с их позициями? Мутновато, имхо, получится, но кто его знает :

Автор: P@sh@ 6.02.2004 12:39

Может CRC посчитать ? например так:

или на паскале:

можно вместо ror поставить rol - числа будут не такими большими...

Автор: UtaH 6.02.2004 13:46

А что такое CRC? ???

Автор: P@sh@ 6.02.2004 14:20

Один из вариантов реализации контрольной суммы (CheckSum):
Cyclical Redundancy Checking (вариант: Code) - циклический контроль с помощью избыточных кодов

PS: тот, что я написал - самый простой вариант... собственно больше и не нужно

Автор: P@sh@ 6.02.2004 14:23

Вероятность, что две хоть чуть-чуть отличающиеся байтовые последовательности будут иметь одинаковую контрольную сумму равна нулю (или почти нулю) - для этого контрольная сумма и была придумана

Автор: trminator 6.02.2004 22:02

Я придумал два варианта: или представлять строку как число в 256-ричной системе счисления (длинноватое число выйдет, хотя, может, в тип comp влезет), или вообще забить на числа и пытаться вместить список слов в динамической памяти.

Автор: trminator 6.02.2004 22:05

Преподы такими придирчивыми бывают... возьмут и специально пример выберут, на котором это самое "почти" и сыплется...
А так она вроде на хэш смахивает... или нет?

Автор: SKVOZNJAK 8.02.2004 14:01

Ну и в чём проблема. Организовать второй этап проверки и отсеять ненужные результаты первого этапа.

Автор: P@sh@ 9.02.2004 10:22

"почти нулю" - это в теории, может для 8-ми битных сумм это может случиться на практике, но для бОльших... Помнится раньше в журналах "Радио" и т.п. печатали программы в машинных HEX-кодах для самодельных компов - и всегда в конце такой таблички (страниц на N) стояла 16-битная контрольная сумма - для проверки. Сейчас в архиваторах наверное 32-битные применяются, как и в TCP-пакетах...

Автор: trminator 9.02.2004 16:56

Тогда это отличный вариант.
Можнешь пояснить, что такое ror? Я так понимаю, что вот оно:
76543210 -> 65432107
(типа ротации что-то). Оно?

Автор: P@sh@ 10.02.2004 8:34

это ROL - сдвиг влево , ROR наоборот
это одна из нескольких ассемблерных команд сдвига
ROR(ROL) - циклический сдвиг(ротация) без захвата флага переноса
есть еще:
RCR(RCL) - циклический сдвиг вместе с флагом переноса(можно и его применить, если вначале сбросить CF)
SHR(SHL) - нециклический сдвиг (в паскале такой оператор есть, бинарный)
есть и еще какие-то экзотические, с подключением второго регистра, но я их не применял ни разу...