Member
Статус: Не в сети Регистрация: 14.08.2004 Откуда: Москва
Доброго времени суток... Вобщем есть такая задачка:
Цитата:
Дан текст длины N символов, содержащий слова, разделенные пробелами, точками и запятыми, причем разделительных символов между словами может быть более одного. Также дано слово-образец длины K. Определить, сколько раз слово-образец встречается в тексте.
Ограничения:
1. 1≤N≤ 500000; 1≤K≤32000
2. Все символы в тексте – маленькие английские буквы, пробелы, точки или запятые.
3. Все символы в слове-образце – маленькие английские буквы.
4. Максимальное время работы программы – 1 секунда.
5. Длина любого слова в тексте не превосходит 32000.
Входные данные:
В первой строчке входных данных находится слово-образец.
Далее на второй строчке содержится текст.
Выходные данные:
Вывести одно число – количество раз, которое слово-образец встречается в тексте.
Например:
Входные данные
abc
abc, def. abc
Выходные данные
2.
Запарился решать... Не могу пролезть в таймлити (1 секунда) при больших числах...
Решаю в делфях так:
Код:
program Project2;
{$APPTYPE CONSOLE}
uses SysUtils;
var a:array[1..500000] of widechar; b:array[1..32000] of widechar; i,j,k:longint; s1,s2:widestring; f:boolean; begin assign(input,'input.txt'); assign(output,'output.txt'); reset(input); rewrite(output); readln(s1); k:=0; for i:=1 to length(s1) do b[i]:=s1[i]; read(s2); for i:=1 to length(s2) do a[i]:=s2[i]; for i:=1 to (length(s2)-length(s1)+1) do begin for j:=1 to length(s1) do begin if b[j]=a[j+i-1] then f:=true else begin f:=false; break; end;
end; if f then begin if ((a[i+j-1]=' ')or(a[i+j-1]='.')or(a[i+j-1]=',')or(i+j-2=length(s2)))and((a[i-1]=' ')or(a[i-1]='.')or(a[i-1]=',')or(i-1=0)) then f:=true else f:=false; end; if f then inc(k); end; writeln(k); close(input); close(output); end.
Кратко объясняю - Первую строку в один массив кладу, вторую в другой... Бегу по второму массиву и сравниваю его элементы с элеменами первого.. Если совпало, проверяю является ли это словом или нет(может это часть слова). Для этого ввожу огромное условие , что после слова должен быть или пробел или точка или запятая, перед ним тоже самое, только тогда увеличиваю количество... Сдаю задачку через программу-тестилку у своего препода на сайте.. Проходит 11 тестов, на 12 вылезает из таймлимита.. Кто-нибудь знает другой алгоритм решения?? Буду оччень благодарен
Advanced member
Статус: Не в сети Регистрация: 23.10.2003 Откуда: Иркутск/Майкоп
Лучше было использовать null-terminated strings (PChar/AnsiString). Для них - стандартную функцию StrPos. Условие записывается (a[i+j-1] in cset) and (a[i-1] in cset) , где const cset:set of char=[' ',',','.'];
_________________ Края каждого совершенно нового крышка процессора не на 100% гладкая. Это связано с тем, что следов мастерства не избежать. (c) Али.
Кто-нибудь знает другой алгоритм решения?? Буду оччень благодарен
Ищет все вхождения слова в файле.
Выводит инфу:
1. Количество найденных слов
2. Время выполнения в ms.
Первая строка в файле – искомое слово (должно соответствовать условию для поиска с разделителями для слов).
Запуск: Search.exe [файл в котором выполняется поиск].
Код:
program Search; // Demo from _SGK :)
{$APPTYPE CONSOLE}
uses Windows, SysUtils, Classes;
var SL: TStringList; CurrentValue: String; ValueForSearch: String; TemporaryValue: String; Outcome: DWORD; OperatingTime: DWORD; StartTime: DWORD; i, j: DWORD; Separators: Set of Char; begin Separators:= [' ', '.', ',']; Outcome:= 0; if ParamCount = 1 then begin if FileExists(ParamStr(1)) then begin StartTime:= GetTickCount; // Перенес начало замера времени. :) SL:= TStringList.Create; try SL.LoadFromFile(ParamStr(1)); if SL.Count >= 2 then begin ValueForSearch:= SL.Strings[0]; for i:= 1 to SL.Count - 1 do begin TemporaryValue:= ''; CurrentValue:= SL.Strings[i]; for j:= 1 to Length(CurrentValue) do begin if not (CurrentValue[j] in Separators) then TemporaryValue:= TemporaryValue + CurrentValue[j] else if TemporaryValue = ValueForSearch then begin Inc(Outcome); TemporaryValue:= ''; end else TemporaryValue:= ''; end; if TemporaryValue = ValueForSearch then Inc(Outcome); end; end; OperatingTime:= GetTickCount - StartTime; finally SL.Free; end; WriteLn(''); WriteLn('Total: ', Outcome); WriteLn('Executed in ', OperatingTime, ' ms.'); WriteLn(''); WriteLn('Press Enter'); ReadLn(CurrentValue); end; end else begin WriteLn('WARNING!'); WriteLn('Usage: Search.exe [filename]'); end; end.
Последний раз редактировалось _SGK 14.12.2005 11:12, всего редактировалось 1 раз.
Member
Статус: Не в сети Регистрация: 14.08.2004 Откуда: Москва
_SGK Сложновато для меня.. завтра на свежую голову разберусь vor Общий смысл понял, но никогда этим не пользовался.. можно мааааленький примерчик? Буду оч благодарен...
_SGK Сложновато для меня.. завтра на свежую голову разберусь
Да ничего сложного нет. Идея проста и стара как мир - исключаем из обработки все избыточное.
cj_remix писал(а):
Сдаю задачку через программу-тестилку у своего препода на сайте.. Проходит 11 тестов, на 12 вылезает из таймлимита.
Саму реализацию поиска особо изящной конечно не назовешь, но она работает – быстро и безглючно, поэтому имеет право на существование.
Данные текстового файла размером в 2526480 байт обрабатывается на моей железяке за ~ 680 ms.
Сравни со своим заданием: 500000 байт и 1 сек на выполнение.
Возьми нужные объявления, реализацию и будет тебе счастье.
Member
Статус: Не в сети Регистрация: 05.07.2004 Откуда: г. Москва
Можно так:
берем первую строку из input для поиска подстроки
кидаем в промежуточный string Stemp
в цикле
пользуем функцию StrPos(слово_для_поиска)
если значение >0 то инкриментируем результат и удаляем из Stemp найденное слово и снова проверяем Stemp
иначе берем вторую строку
разделители не мешают - strpos ищет подстроку полностью.
значит если слово_для_поиска не содержит разделителей - проблем не будет
можно не удалять, а копировать в Stemp остаток Stemp после последнего символа слово_для_поиска - это даст все уменьшающееся время работы strpos на итерацию
можно не загружать в TStringList, а использовать blockread прямо из файла в цикле - довольно быстрая функция чтения.
зачем лишние "телодвижения"? Впрочем...что быстрее, blockread или загрузить в TStringList - надо проверять на практике.
_________________ "Не припадайте к статуям, нет правды в их ногах."
Особенно позабавило. Вот люблю я теоретиков, без них жизнь не жизнь. Чем грузить, какая нафиг разница? В конечном счете все будет загружено в выделенную область памяти и будет использован определенный вариант доступа.
Существенных моментов всего два: 1. Выполнить корректно поиск и уложиться во временной интервал выделенный для выполнения. 2. При проверке задания у препода не должно возникнуть сомнений относительно авторства работы.
SergGreen писал(а):
надо проверять на практике.
Это точно.
Мот поделишься результатом? Жательно в коде.
Member
Статус: Не в сети Регистрация: 05.07.2004 Откуда: г. Москва
_SGK Причем тут теория?
Похожим способом (blockread) я "разбирал на части" dbf-ку. Конкретную конечно, строго определенной структуры.
Проще и быстрее оказалось, чем через BDE. НАМНОГО быстрее.
Впрочем, когд-то я экспериментировал с загрузкой данных в . Через blockread, и стандартный LoadFromFile. Скорость была одинакова. На величину погрешности.
У тебя притензии по алгоритму или по способу чтения в память?:)
К сожалению код привести не могу - сейчас программированием не занимаюсь. На рабочем месте Delphi нет.
Но смысл алгоритма простой:
в цикле
берем строку
ищем в ней слово
если находим увеличиваем результат и удаляем _найденное_ слово чтобы не мешало
ищем в получившейся строке снова
выход из цикла - если слово больше не найдено
получаем уменьшение строки на каждой итерации - уменьшение времени поиска
а испоьзование массивов не имеет смысла - string(все типы) по сути те же массивы.
_________________ "Не припадайте к статуям, нет правды в их ногах."
Похожим способом (blockread) я "разбирал на части" dbf-ку.
Даже не знаю, для кого бы это могло быть новостью. Если бы ты не поленился глянуть в исходники по реализации работы с *.dbf времен BP7, то увидел бы, что еще тогда, отдельными гражданами все именно так и было реализовано.
SergGreen писал(а):
Проще и быстрее оказалось, чем через BDE. НАМНОГО быстрее.
Очень хорошо, но причем здесь вообще BDE? К нашей конкретной задаче твое сравнение, каким боком?
SergGreen писал(а):
Причем тут теория?
Да так, к слову… При решении любой задачи обычно присутствуют как первичные, так и вторичные моменты. Ессно я соглашусь, что построение списка займет больше времени, чем просто выделение памяти и закачка туда данных. Но! Разница будет ничтожно мала. Сэкономишь десяток ms для многострочного файла, это так принципиально?
SergGreen писал(а):
К сожалению код привести не могу - сейчас программированием не занимаюсь. На рабочем месте Delphi нет. Но смысл алгоритма простой:
SergGreen писал(а):
в цикле берем строку ищем в ней слово
Как ищем и проверяем то, что найденное значение является именно словом, а не частью другого слова?
SergGreen писал(а):
если находим увеличиваем результат и удаляем _найденное_ слово чтобы не мешало ищем в получившейся строке снова
А ели нужных вхождений в строке 10000 или 100000. Так и будешь их все удалять? Смотри внимательно условие задачи. Нигде не сказано ни о минимальном размере значения строки для поиска, ни об ограничении на количество вхождений искомой строки в тексте. Добавлено спустя 2 минуты, 13 секунд
SergGreen писал(а):
У тебя притензии по алгоритму или по способу чтения в память?
Member
Статус: Не в сети Регистрация: 05.07.2004 Откуда: г. Москва
_SGK
Цитата:
Как ищем и проверяем то, что найденное значение является именно словом, а не частью другого слова?
вот что значит код не написать а просто придумать:)
забыл учесть...хотя учесть в моем алгоритме тоже не сложно:
вычислить заранее длинну слова как L
значение strpos сохранять в переменную P и проверять значения string[P-1] и string[P+L+1] на вхождение в список сепараторов
впрочем, я внимательно разобрал твой вариант, слегкостью признаю - он оптимальней!:)
...да...давно я "не брал в руки шашек"...:):)
_________________ "Не припадайте к статуям, нет правды в их ногах."
Member
Статус: Не в сети Регистрация: 14.08.2004 Откуда: Москва
Пацаны - пасибо всем за помощь и советы... но тут мой препод прогнал То что я написал прошло на ура, его тестилка просто тогда глюкнула... Всем спасибо Добавлено спустя 3 минуты, 19 секунд Точнее, не совсем то что написал.. Там ещё если нашёл слово, то поиск начинай со следующего слова.. что почти одно и тоже, что написал SergGreen
SergGreen писал(а):
если находим увеличиваем результат и удаляем _найденное_ слово чтобы не мешало
Member
Статус: Не в сети Регистрация: 11.03.2004 Откуда: Moscow
ребят, помогите и мне кому не сложно.
delphi, списки.
есть такое заданьице:
Вводится произвольный текст из неизвестного количества строк. Конец текста отмечается точкой. Представить текст в виде списка строк. Длина каждой строки в элементе списка не превышает 30 символов. Более длинные строки в список не заносить. Определить число строк для списка, обеспечить перестановку i-й и j-й строк.
Я собственно почти все сделал, вот только с перестановкой запутался. мож кто подскажет?
Если ты вдруг под списком сток имеешь в виду абстрактный класс TStrings и хочешь работать с одним из его наследников, к примеру с TStringList, то для перестановки элементов списка можно использовать метод Exchange (что, впрочем, справедливо и для TList – список указателей).
Пример:
Код:
procedure TForm1.Button1Click(Sender: TObject); var SL: TStringList; begin SL:= TStringList.Create; try SL.Add('бла-бла-бла'); SL.Add('учим ООП'); SL.Add('срочно'); SL.Exchange(0, SL.Count -1); SL.SaveToFile('C:\бла-бла-бла.txt'); // Смотрим результат ;) finally SL.Free; end; end;
Member
Статус: Не в сети Регистрация: 11.03.2004 Откуда: Moscow
_SGK не, я не так объяснил консольная дельфя.
короче вот что есть:
Код:
program Project2;
{$APPTYPE CONSOLE}
uses SysUtils;
type list_d=record pole:string[100]; end;
ff=file of list_d; pel_list=^list; list=record li:list_d; next:pel_list; end; var lp,plist,pstart:pel_list; f:ff; li:list_d; i,n,str_v_t,str_v_l:integer; procedure init; begin pstart:=nil; end; procedure insert_list_fr_file(el: list_d; var svl:integer); begin new(pList); if pStart=nil then begin if length(el.pole)<=30 then begin with pList^ do begin li.pole:=el.pole; next:=nil; end; pstart:=plist; lp:=plist; end; end else begin if length(el.pole)<=30 then begin lp^.next:=plist; with pList^ do begin li.pole:=el.pole; next:=nil; end; lp:=plist; svl:=svl+1; end; end; end;
procedure list_create(var stvl:integer); begin init; assign(f,'file.dat'); reset(f); while not eof(f) do begin read(f,li); insert_list_fr_file(li,stvl); end; end; procedure list_vivod; var i:integer; begin i:=1; lp:=pstart; writeln('std'); while lp<>nil do begin writeln(lp^.li.pole); lp:=lp^.next; i:=i+1; end; end; procedure del_list; begin lp:=pstart; while lp<>nil do begin plist:=lp; dispose(plist); lp:=lp^.next; end; end;
procedure save_to_file(var svt:integer); var k:char; i,n:integer; s:string; begin assign(f,'file.dat'); rewrite(f); repeat with li do begin readln(pole); s:=pole; end; write(f,li); svt:=svt+1; until s[length(s)]='.'; end;
begin { TODO -oUser -cConsole Main : Insert code here }
//здесь будет типа меню с помощью Case of и будут вызываться все эти процедуры. save_to_file(str_v_t); list_create(str_v_l); list_vivod; writeln('strok v texte: ',str_v_t); writeln('strok v spiske: ',str_v_l+1); // del_list; readln; end.
и вот надо заставить это менять любые две строки в списке по желанию пользователя.
Набросал процедуру под твой код.
Глянь, подправь, где нужно, бо как говаривал один мой знакомый: "Когда болею, то бываю просто гениален".
Код:
procedure list_Exchange(Index1, Index2: Longword); var i: Longword; p1, p2: Pointer; begin if Index1 > Index2 then begin i:= Index1; Index2:= Index1; Index1:= i; end; GetMem(p2, SizeOf(lp^.li.pole)); try i:= 1; lp:= pstart; while lp <> nil do begin if i = Index1 then p1:= @lp^.li.pole; if i = Index2 then begin CopyMemory(p2, @lp^.li.pole, SizeOf(lp^.li.pole)); CopyMemory(@lp^.li.pole, p1, SizeOf(lp^.li.pole)); CopyMemory(p1, p2, SizeOf(lp^.li.pole)); Break; end; lp:= lp^.next; Inc(i); end; finally FreeMem(P2, SizeOf(lp^.li.pole)); end; end;
Соответственно в вызов при существующем списке, а к uses добавить Windows.
Код:
begin { TODO -oUser -cConsole Main : Insert code here }
//здесь будет типа меню с помощью Case of и будут вызываться все эти процедуры. save_to_file(str_v_t); list_create(str_v_l); list_Exchange(1, 2); // Перестанавливает. list_vivod; writeln('strok v texte: ',str_v_t); writeln('strok v spiske: ',str_v_l+1); // del_list; readln; end.
Member
Статус: Не в сети Регистрация: 13.06.2005 Откуда: Украина, Глухов
_SGK@LF вставлю свои пять копеек _SGK считаю лишним двигать данные в памяти.
поскольку используются указатели, проще и надежнее просто поменять указатели на необходимые структуры.
_________________ Что-то начнется, что-то закончится...
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения