Текущий архив: 2004.02.17;
Скачать: CL | DM;
Вниз
Поиск слова Найти похожие ветки
← →
JediMaster (2004-02-05 17:02) [0]Здравствуйте!
Есть текст и есть слова. Так вот в тексте нужно найти строку и символ, где впервые попадается любое из слов.
Так вот вопрос в том, как можно произвести поиск!
Я делал так: брал слово и получал его "код" - for i:=1 to length(s) do codes[i]:=codes[i]+ord[s]; и проходил полностью весь текст.
Проблема в том, что если слово другое, но одинаковые буквы в нем, пример: drea и read.
А целиком слово я хранить не могу, т.к. общее количество слов достигает 1000, да притом все делается на Паскале.
Ограничения такие: максимальное число слов: 1000. Текст 400Кб
Как можно еще попробовать ?
← →
h0use © (2004-02-05 17:22) [1]Попробуй загружать в TRichEdit и там используй FindText
← →
JediMaster (2004-02-05 17:23) [2]Мне нужно это на Паскале, а не в Дельфи !! :)
← →
h0use © (2004-02-05 17:32) [3]тогда Pos(S1,S2) ищи. Он тебе выдаст индекс, где впервые строка S1 встречается в строке S2
← →
JediMaster (2004-02-05 17:34) [4]Ну а как тогда представить слова, ведь тх может быть около 1000?
В паскале в Массив не влезет!!!!!
← →
Тимохов © (2004-02-05 17:38) [5]схема такая
var
s: string;
i,j,k: integer;
w: array[0..999] of stirng;
foundpos: integer;
begin
s := "текст в котором ищем"
w := "заполняешь словами, которые ищем. важно, что слова не пустые";
for i := 1 to length(s) do
begin
for j := 0 to 999 do
begin
if s[i] = w[j][1] then
begin
foundpos := i;
for k := 2 to length(w[j]) do
begin
if (i+k-1 > length(s)) or (s[i+k-1] <> w[j][k]) then
begin
foundpos := 0;
break;
end;
end;
if foundpos >= 1 then
begin
ура! нашли - это foundpos - делай с ним, что хочешь.
exit;
end;
end;
end;
end;
end;
Вроде так. Не понятно, как ты будешь в паскале хранить такую длинную строку - но, думаю
сам разберешься.
Еще можно выполнить pos для каждого слова из списка и взять минимальное значение.
Если есть очепатики - простите, писал тут.
← →
h0use © (2004-02-05 17:38) [6]Почему не влезет? Там ограничение кол-ва элементов кажись Integer, т.е. 64к элементов.
← →
Тимохов © (2004-02-05 17:41) [7]
> Почему не влезет? Там ограничение кол-ва элементов кажись
> Integer, т.е. 64к элементов
Если не ошибаюсь там ограничение на общее количество байтов в структуре - т.е по 256 байт на каждую строку. Итого примерно 256 кб :(((
АВТОРУ:
Алгоритм я тебе дал.
Можешь заменимть массивы динамическими структурами. Если не ошибаюсь в pascal были getmem и freemem?
← →
JediMaster (2004-02-05 17:42) [8]2house
Пичем integer, ведь даны строки? Если хранить ихнеи коды, то я описал причину
← →
JediMaster (2004-02-05 17:42) [9]Thx
← →
Тимохов © (2004-02-05 17:45) [10]
> JediMaster (05.02.04 17:42) [9]
Не помню есть ли в паскале опция компилятора "complete boolean evaluation". В своем алгоритме я заложился на то, что она отключена...
← →
JediMaster (2004-02-05 17:49) [11]ДА ЭТА ОПЦИЯ ЕСТЬ !
← →
AKul © (2004-02-05 17:55) [12]
> h0use © (05.02.04 17:38) [6]
> Почему не влезет? Там ограничение кол-ва элементов кажись
> Integer, т.е. 64к элементов.
Не мешало бы Вам познакомиться с организацией памяти в реальном режиме x86 процессоров.
To JediMaster (05.02.04 17:02)
Что мешает эти строки хранить в массиве типа Char, которые разделять пробелами или нулями.
Можно объявить массив из строк, но не просто из String (который занимает 256 байт), а например из String[15].
Итого 16*1000 = 16000 байт - свободно влезаем в Segment.
Наконец, можно воспользоваться динамически выделяемой памятью, создать массив из указателей или организовать список....
Главное - бы было желание....
← →
JediMaster (2004-02-05 18:00) [13]Если не трудно, то расскажите про списки поподробнее, пожалуйста :)
← →
Alexander666 © (2004-02-05 18:10) [14]Есть статья на RSDN "Алгоритмы поиска текста". Вот там и посмотри.
← →
JediMaster (2004-02-05 18:38) [15]Вот ограничения:
Первая строка содержит число N (1 <= N <= 10000) — количество слов. Следующие N строк содержат список слов, использование которых в нашем культурном обществе считается недопустимым. В слове могут встречаться любые символы, кроме символов с кодами 0, 10 и 13. Длина каждого слова не превышает 10000 символов. Общий объём слов не превышает 100 КБ. После этого идёт число M — количество строк в тексте. Общий объём текста не превышает 900 КБ.
Блин, даже предсатвить не могу как хранить 10000 слов с длиной 10000. Подскажите кто-нибудь !
← →
Тимохов © (2004-02-05 18:50) [16]Фиг с ним с хранением - ты прикинь сколько это работать по времени будет.
Думаю тут нужны специальные алгоритмы. Думаю, вам стоит прислушаться к 15.
← →
Тимохов © (2004-02-05 18:51) [17]Т.е. к 14
Страницы: 1 вся ветка
Текущий архив: 2004.02.17;
Скачать: CL | DM;
Память: 0.5 MB
Время: 0.027 c
