Олимпиадная задача PASCAL

@viventus_43 · Регистрация: 28.11.2019

Студворк — интернет-сервис помощи студентам

D. Заклинание
Ограничение времени: 1 секунда
Ограничение памяти: 64Mb
Ввод: spell.in
Вывод: spell.out

В Хогвартсе на уроках магии дети постигают науку формулировки заклинаний. На одном из последних занятий они познакомились с понятием магической силы заклинания. Магическая сила заклинания равна количеству повторений в этом заклинании основного магического сочетания символов. Например, если магическое сочетание "qqq то заклинание "qqqq"обладает магической силой 2, заклинание "qqrqq магической силой 0, а заклинание "qqwrnqqqjkookqqqiqqq магической силой 3. Напишите, пожалуйста программу, вычисляющую магическую силу заклинания.

Формат ввода:
Первая строка входного файла spell.in сожержит основное магическое сочетание - последовательность латинских строчных букв длиной не менее 2 и не более 300 символов. Вторая строка содержит заклинание - последовательность латинских строчных букв длиной не менее 2 и не более 3350000 символов.

Формат вывода:
В файл spell.out выведите единственное число - магическую силу заклинания.

Пример
Ввод:
ba
baaaabbabar
Вывод:
3

Примечания
Вы можете получить до 80 баллов за решение, которое работает для заклинаний длиной не более 1000 символов. Вы можете получить до 60 баллов за решение, которое работает для заклинаний длиной не более 400 символов.

@Sun Serega · 29.11.2019, 04:05

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
{$string_nullbased+}
 
function TestBuff(buff: array of char; ind: integer; ss: string): boolean;
begin
  for var i := 0 to buff.Length-1 do
    if ss[i] <> buff[ (i+ind) mod buff.Length ] then exit;
  Result := true;
end;
 
begin
  
  var sr := System.IO.File.OpenText('spell.in');
  // для тестов
//  var sr := new System.IO.StringReader(
//    'ba'#10
//    'baaaabbabar'
//  );
  
  var ss := sr.ReadLine;
  var c := 0;
  var buff := new char[ss.Length];
  
  if sr.ReadBlock(buff,0,buff.Length)=buff.Length then
  begin
    var i := 0;
    
    while true do
    begin
      if TestBuff(buff,i,ss) then c += 1;
      var ch := sr.Read;
      if ch=-1 then break;
      buff[i] := char(ch);
      i := (i+1) mod buff.Length;
    end;
    
  end;
  
  WriteAllText('spell.out', c.ToString);
//  c.Println; // тоже для тестов
  
end.

@mr-Crocodile · 29.11.2019, 12:21

Сообщение от Sun Serega

var ss := sr.ReadLine;

ss переменная легко вместит 3 с лишним Мб ?
а после этого

Сообщение от Sun Serega

var buff := new char[ss.Length];

буфер ещё на 3 с лишним Мб ?
Без проблем?

@eaa · 29.11.2019, 13:16

mr-Crocodile, а зачем КМП писать?!

@mr-Crocodile · 29.11.2019, 13:25

Сообщение от eaa

mr-Crocodile, а зачем КМП писать?!

пришлось загуглить.

Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — эффективный алгоритм, осуществляющий поиск подстроки в строке. Время работы алгоритма линейно зависит от объёма входных данных, то есть разработать асимптотически более эффективный алгоритм невозможно.

@Sun Serega · 30.11.2019, 00:31

Сообщение от mr-Crocodile

ss переменная легко вместит 3 с лишним Мб ?

Вы так говорите, как будто это проблема. Ограничение памяти 64Мб.
И не важно какой алгоритм брать, образец всё равно надо сохранить 1 раз целиком. Читать из файла каждый раз будет и сложнее и дороже.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .

@viventus_43 0 / 0 / 0 Регистрация: 28.11.2019 Сообщений: 1

	Олимпиадная задача PASCAL 28.11.2019, 09:37. Показов 1166. Ответов 5 Метки pascal abc, олимпиада pascal (Все метки) D. Заклинание Ограничение времени: 1 секунда Ограничение памяти: 64Mb Ввод: spell.in Вывод: spell.out В Хогвартсе на уроках магии дети постигают науку формулировки заклинаний. На одном из последних занятий они познакомились с понятием магической силы заклинания. Магическая сила заклинания равна количеству повторений в этом заклинании основного магического сочетания символов. Например, если магическое сочетание "qqq то заклинание "qqqq"обладает магической силой 2, заклинание "qqrqq магической силой 0, а заклинание "qqwrnqqqjkookqqqiqqq магической силой 3. Напишите, пожалуйста программу, вычисляющую магическую силу заклинания. Формат ввода: Первая строка входного файла spell.in сожержит основное магическое сочетание - последовательность латинских строчных букв длиной не менее 2 и не более 300 символов. Вторая строка содержит заклинание - последовательность латинских строчных букв длиной не менее 2 и не более 3350000 символов. Формат вывода: В файл spell.out выведите единственное число - магическую силу заклинания. Пример Ввод: ba baaaabbabar Вывод: 3 Примечания Вы можете получить до 80 баллов за решение, которое работает для заклинаний длиной не более 1000 символов. Вы можете получить до 60 баллов за решение, которое работает для заклинаний длиной не более 400 символов. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	29.11.2019, 13:16
	mr-Crocodile, а зачем КМП писать?! 1