IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Поиск слова
сообщение
Сообщение #1


Гость






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

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

Как можно еще попробовать ?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Четыре квадратика
****

Группа: Пользователи
Сообщений: 579
Пол: Мужской

Репутация: -  4  +


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


--------------------
Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


человек-нерпа
***

Группа: Пользователи
Сообщений: 286
Пол: Женский

Репутация: -  13  +


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


--------------------
I am riding a Thesaurus!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Бывалый
***

Группа: Пользователи
Сообщений: 180
Пол: Мужской

Репутация: -  2  +


Может 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 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


человек-нерпа
***

Группа: Пользователи
Сообщений: 286
Пол: Женский

Репутация: -  13  +


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


--------------------
I am riding a Thesaurus!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Бывалый
***

Группа: Пользователи
Сообщений: 180
Пол: Мужской

Репутация: -  2  +


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

PS: тот, что я написал - самый простой вариант... собственно больше и не нужно
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Бывалый
***

Группа: Пользователи
Сообщений: 180
Пол: Мужской

Репутация: -  2  +


Вероятность, что две хоть чуть-чуть отличающиеся байтовые последовательности будут иметь одинаковую контрольную сумму равна нулю (или почти нулю) - для этого контрольная сумма и была придумана
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Четыре квадратика
****

Группа: Пользователи
Сообщений: 579
Пол: Мужской

Репутация: -  4  +


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


--------------------
Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Четыре квадратика
****

Группа: Пользователи
Сообщений: 579
Пол: Мужской

Репутация: -  4  +


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

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


--------------------
Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Профи
****

Группа: Пользователи
Сообщений: 930
Пол: Мужской

Репутация: -  11  +


Ну и в чём проблема. Организовать второй этап проверки и отсеять ненужные результаты первого этапа.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Бывалый
***

Группа: Пользователи
Сообщений: 180
Пол: Мужской

Репутация: -  2  +


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


Четыре квадратика
****

Группа: Пользователи
Сообщений: 579
Пол: Мужской

Репутация: -  4  +


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


--------------------
Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Бывалый
***

Группа: Пользователи
Сообщений: 180
Пол: Мужской

Репутация: -  2  +


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

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 




- Текстовая версия 25.09.2017 4:21
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"