Поиск слова Опции

[Серг]

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

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

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

[trminator]

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

[UtaH]

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

[P@sh@]

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

Код

ror  word ptr [CheckSum],1
movzx  ax,byte ptr es:[di]
add  word ptr [CheckSum],ax

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

Код

var crc: word;
...
crc:=0;
for i:=1 to length(s) do begin
asm ror crc,1 end;
crc:=crc+ord(s[i]);
end;
...

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

Сообщение отредактировано: volvo - 18.12.2004 2:29

[UtaH]

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

[P@sh@]

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

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

[P@sh@]

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

[trminator]

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

[trminator]

или почти нулю

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

[SKVOZNJAK]

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

[P@sh@]

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

[trminator]

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

[P@sh@]

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