Часовой пояс: UTC + 3 часа




Начать новую тему Новая тема / Ответить на тему Ответить  Сообщений: 27 • Страница 1 из 21  2  >
  Пред. тема | След. тема 
В случае проблем с отображением форума, отключите блокировщик рекламы
Автор Сообщение
 

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) Али.


 

Member
Статус: Не в сети
Регистрация: 05.01.2005
cj_remix
cj_remix писал(а):
Кто-нибудь знает другой алгоритм решения?? Буду оччень благодарен

Ищет все вхождения слова в файле.
Выводит инфу:
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
Общий смысл понял, но никогда этим не пользовался.. можно мааааленький примерчик? Буду оч благодарен...


 

Member
Статус: Не в сети
Регистрация: 05.01.2005
cj_remix
cj_remix писал(а):
_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 - надо проверять на практике.

_________________
"Не припадайте к статуям, нет правды в их ногах."


 

Member
Статус: Не в сети
Регистрация: 05.01.2005
SergGreen
SergGreen писал(а):
зачем лишние "телодвижения"?

Особенно позабавило. :)
Вот люблю я теоретиков, без них жизнь не жизнь.
Чем грузить, какая нафиг разница?
В конечном счете все будет загружено в выделенную область памяти и будет использован определенный вариант доступа.

Существенных моментов всего два:
1. Выполнить корректно поиск и уложиться во временной интервал выделенный для выполнения.
2. При проверке задания у препода не должно возникнуть сомнений относительно авторства работы.

SergGreen писал(а):
надо проверять на практике.

Это точно.
Мот поделишься результатом? Жательно в коде. :)


 

Member
Статус: Не в сети
Регистрация: 05.07.2004
Откуда: г. Москва
_SGK
Причем тут теория?
Похожим способом (blockread) я "разбирал на части" dbf-ку. Конкретную конечно, строго определенной структуры.
Проще и быстрее оказалось, чем через BDE. НАМНОГО быстрее.
Впрочем, когд-то я экспериментировал с загрузкой данных в . Через blockread, и стандартный LoadFromFile. Скорость была одинакова. На величину погрешности.:)

У тебя притензии по алгоритму или по способу чтения в память?:)

К сожалению код привести не могу - сейчас программированием не занимаюсь. На рабочем месте Delphi нет.
Но смысл алгоритма простой:
в цикле
берем строку
ищем в ней слово
если находим увеличиваем результат и удаляем _найденное_ слово чтобы не мешало
ищем в получившейся строке снова
выход из цикла - если слово больше не найдено

получаем уменьшение строки на каждой итерации - уменьшение времени поиска
а испоьзование массивов не имеет смысла - string(все типы) по сути те же массивы.

_________________
"Не припадайте к статуям, нет правды в их ногах."


 

Member
Статус: Не в сети
Регистрация: 05.01.2005
SergGreen
SergGreen писал(а):
Похожим способом (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
Откуда: Москва
Пацаны - пасибо всем за помощь и советы... но тут мой препод прогнал :) То что я написал прошло на ура, его тестилка просто тогда глюкнула... Всем спасибо :beer:
Добавлено спустя 3 минуты, 19 секунд
Точнее, не совсем то что написал.. Там ещё если нашёл слово, то поиск начинай со следующего слова.. что почти одно и тоже, что написал SergGreen
SergGreen писал(а):
если находим увеличиваем результат и удаляем _найденное_ слово чтобы не мешало


 

Member
Статус: Не в сети
Регистрация: 11.03.2004
Откуда: Moscow
ребят, помогите и мне кому не сложно.

delphi, списки.
есть такое заданьице:

Вводится произвольный текст из неизвестного количества строк. Конец текста отмечается точкой. Представить текст в виде списка строк. Длина каждой строки в элементе списка не превышает 30 символов. Более длинные строки в список не заносить. Определить число строк для списка, обеспечить перестановку i-й и j-й строк.

Я собственно почти все сделал, вот только с перестановкой запутался. мож кто подскажет?

_________________
6800LE 16x1, 6vp 3DMark03 - 14000, 3DMark05 - 5942


 

Member
Статус: Не в сети
Регистрация: 05.01.2005
@LF
@LF писал(а):
Я собственно почти все сделал, вот только с перестановкой запутался. мож кто подскажет?

Посмотри метод Exchange. :wink:


 

Member
Статус: Не в сети
Регистрация: 11.03.2004
Откуда: Moscow
_SGK не понял, можно подробней?

_________________
6800LE 16x1, 6vp 3DMark03 - 14000, 3DMark05 - 5942


 

Member
Статус: Не в сети
Регистрация: 05.01.2005
@LF
@LF писал(а):
не понял, можно подробней?

Если ты вдруг :wink: под списком сток имеешь в виду абстрактный класс 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.

и вот надо заставить это менять любые две строки в списке по желанию пользователя.

_________________
6800LE 16x1, 6vp 3DMark03 - 14000, 3DMark05 - 5942


 

Member
Статус: Не в сети
Регистрация: 05.01.2005
@LF
@LF писал(а):
не, я не так объяснил консольная дельфя.

А какая разница? :spy:

Набросал процедуру под твой код.
Глянь, подправь, где нужно, бо как говаривал один мой знакомый: "Когда болею, то бываю просто гениален". :haha:

Код:
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
считаю лишним двигать данные в памяти.
поскольку используются указатели, проще и надежнее :) просто поменять указатели на необходимые структуры.

_________________
Что-то начнется, что-то закончится...


 

Member
Статус: Не в сети
Регистрация: 11.03.2004
Откуда: Moscow
_SGK спасибо. сейчас буду разбираться в этом.
Добавлено спустя 3 минуты, 25 секунд
wCat
Цитата:
просто поменять указатели на необходимые структуры

вот собственно это и надо, но я в них запутался.

_________________
6800LE 16x1, 6vp 3DMark03 - 14000, 3DMark05 - 5942


 

Member
Статус: Не в сети
Регистрация: 05.01.2005
wCat
wCat писал(а):
считаю лишним двигать данные в памяти.
поскольку используются указатели, проще и надежнее просто поменять указатели на необходимые структуры.

А еще лучше сразу все писать как надо. :)

@LF
@LF писал(а):
вот собственно это и надо, но я в них запутался.

&
@LF писал(а):
обеспечить перестановку i-й и j-й строк.

Мдя…


Показать сообщения за:  Поле сортировки  
Начать новую тему Новая тема / Ответить на тему Ответить  Сообщений: 27 • Страница 1 из 21  2  >
-

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB | Kolobok smiles © Aiwan