Текстовый файл состоит не более чем из 10 6 заглавных латинских букв az
Обновлено: 07.07.2024
Алгоритмы на строках
A. Сравнения подстрок
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Дана строка. Нужно уметь отвечать на запросы вида: равны ли подстроки [a..b] и [c..d].
Сперва строка S (не более 10^5 строчных латинских букв). Далее число M — количество запросов.
M строк. Выведите Yes, если подстроки совпадают, и No иначе.
входные данные
выходные данные
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Постройте префикс-функцию для заданной строки s.
Первая строка входного файла содержит s (1 ≤ |s| ≤ 10^6). Строка состоит из букв латинского алфавита.
Выведите значения префикс-функции строки s для всех индексов 1, 2, . |s|.
входные данные
выходные данные
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Постройте Z-функцию для заданной строки s.
Первая строка входного файла содержит s (1 ≤ |s| ≤ 10^6). Строка состоит из букв латинского алфавита.
Выведите значения Z-функции строки s для индексов 2, 3, . |s|.
входные данные
выходные данные
входные данные
выходные данные
D. Быстрый поиск подстроки в строке
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Даны строки p и t. Требуется найти все вхождения строки p в строку t в качестве подстроки.
Первая строка входного файла содержит p, вторая — t (1 ≤ |p|, |t| ≤ 10^6). Строки состоят из букв латинского алфавита.
В первой строке выведите количество вхождений строки p в строку t. Во второй строке выведите в возрастающем порядке номера символов строки t, с которых начинаются вхождения p. Символы нумеруются с единицы.
входные данные
выходные данные
E. Поиск периода
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Дана строка s. Требуется найти минимальную по длине строку t, такую что s представима в виде конкатенации одной или нескольких строк t.
Первая строка входного файла содержит s (1 ≤ |s| ≤ 10^6). Строка состоит из букв латинского алфавита.
Выведите длину искомой строки t.
входные данные
выходные данные
входные данные
выходные данные
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Даны K строк из маленьких латинских букв. Требуется найти их наибольшую общую подстроку.
В первой строке число K (1 ≤ K ≤ 10).
В следующих K строках — собственно K строк (длины строк от 1 до 10 000).
Наибольшая общая подстрока.
входные данные
выходные данные
G. Множественный поиск
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: search4.in
вывод: search4.out
Дан массив строк si и строка t. Требуется для каждой строки si определить, встречается ли она в t как подстрока.
Первая строка входного файла содержит целое число n — число элементов в s (1 ≤ n ≤ 10^6). Следующие n строк содержат по одной строке si. Сумма длин всех строк из s не превосходит 10^6. Последняя строка входного файла содержит t (1 ≤ t ≤ 10^6). Все строки состоят из строчных латинских букв.
Для каждой строки si выведите «YES», если она встречается в t и «NO» в противном случае. Строки нумеруются в порядке появления во входном файле.
входные данные
выходные данные
H. Множественный поиск 2
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: search5.in
вывод: search5.out
Дан массив строк si и строка t. Требуется для каждой строки si определить, сколько раз она встречается в t как подстрока.
Первая строка входного файла содержит целое число n — число элементов в s (1 ≤ n ≤ 10^6). Следующие n строк содержат по одной строке si. Сумма длин всех строк из s не превосходит 10^6. Последняя строка входного файла содержит t (1 ≤ t ≤ 10^6). Все строки состоят из строчных латинских букв
Для каждой строки si выведите одно число: сколько раз она встречается в t. Строки нумеруются в порядке появления во входном файле.
входные данные
выходные данные
I. Множественный поиск 3
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 512 мегабайт
ввод: search6.in
вывод: search6.out
Дан массив строк si и строка t. Требуется для каждой строки si найти самое левое и самое правое вхождение в t как подстроки.
Первая строка входного файла содержит целое число n — число элементов в s (1 ≤ n ≤ 10^6). Следующие n строк содержат по одной строке si. Сумма длин всех строк из s не превосходит 10^6. Последняя строка входного файла содержит t (1 ≤ t ≤ 10^6). Все строки состоят из строчных латинских букв.
Для каждой строки si выведите два числа: индексы самой левой и самой правой позиции, в которых она встречается в t. Если строка не встречается в t ни разу, выведите - 1 - 1. Строки нумеруются в порядке появления во входном файле. Позиции нумеруются с 0.
входные данные
выходные данные
J. Суффиксный массив
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 512 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Постройте суффиксный массив для заданной строки s, для каждых двух соседних суффиксов найдите длину максимального общего префикса.
Первая строка входного файла содержит строку s (1 ≤ |s| ≤ 400 000). Строка состоит из строчных латинских букв.
В первой строке выведите |s| различных чисел — номера первых символов суффиксов строки s так, чтобы соответствующие суффиксы были упорядочены в лексикографически возрастающем порядке. Во второй строке выведите |s| - 1 чисел — длины наибольших общих префиксов.
входные данные
выходные данные
K. Количество подстрок
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 512 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Вычислите количество различных подстрок строки s.
Единственная строка входного файла содержит строку s (1 ≤ |s| ≤ 400 000). Строка состоит из строчных латинских букв.
Выведите одно число — ответ на задачу.
входные данные
выходные данные
L. Циклические сдвиги
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 512 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
k-м циклическим сдвигом строки S называется строка, полученная перестановкой k первых символов строки S в конец строки.
Рассмотрим все различные циклические сдвиги строки S и отсортируем их по возрастанию. Требуется вычислить i-ю строчку этого массива.
Например, для строки abacabac существует четыре различных циклических сдвига: нулевой (abacabac), первый (bacabaca), второй (acabacab) и третий (cabacaba). После сортировки по возрастанию получится такой массив: abacabac, acabacab, bacabaca, cabacaba.
В первой строке входного файла записана строка S, длиной не более 100 000 символов с ASCII-кодами от 32 до 126. Во второй строке содержится единственное целое число k (1 ≤ k ≤ 100 000).
В выходной файл выведите k-й по возрастанию циклический сдвиг строки S, или слово IMPOSSIBLE, если такого сдвига не существует.
входные данные
выходные данные
входные данные
выходные данные
M. Наибольшая общая подстрока
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 512 мегабайт
ввод: common.in
вывод: common.out
Найдите наибольшую общую подстроку строк s и t.
Первая строка входного файла содержит строку s, вторая — t (1 ≤ |s|, |t| ≤ 100,000). Строки состоят из строчных латинских букв.
Выведите одну строку — наибольшую общую подстроку строк s и t. В случае, если ответ не единственный, выведите минимальный лексикографически.
Проверяемые элементы содержания: Умение создавать собственные программы (10–20 строк) для обработки символьной информации
Выполнение 24 задания ЕГЭ
Плейлист видеоразборов задания на YouTube:
Последовательности (цепочки) символов
24 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Текстовый файл состоит не более чем из 106 символов X, Y и Z.
Определите максимальное количество идущих подряд символов, среди которых каждые два соседних различны.
Для выполнения этого задания следует написать программу.
var f: text; i, k, max: integer; s: string; begin assign(f, 'D:\24.txt'); reset(f); readln(f, s); max := 1; k := 1; // кол-во подряд идущих for i := 2 to length(s) do begin if s[i] <> s[i - 1] then begin inc(k); if k > max then max := k; end else k := 1; end; write(max) end.
f=open('D:/24.txt') s=f.readline() m=1 k=1 for i in range(1,len(s)): if s[i]!=s[i-1]: k+=1 m=max(k,m) else: k=1 print(m)
Видеоразбор:
24 задание с сайта К. Полякова, № 1:
В текстовом файле k7-0.txt находится цепочка из символов латинского алфавита A, B, C.
Найдите длину самой длинной подцепочки, состоящей из символов C.
Ответ: 0
begin assign(input, 'k7-0.txt'); var s: string; var c: string; read(s); c := 'C'; while c in s do c := c + 'C'; print(length(c) - 1) end.
24 задание с сайта К. Полякова, № 21:
В текстовом файле k7a-1.txt находится цепочка из символов латинского алфавита A, B, C, D, E.
Найдите длину самой длинной подцепочки, состоящей из символов A, B или C (в произвольном порядке).
Ответ: 16
begin assign(input, 'k7a-1.txt'); var s: string; read(s); var k := 0; var maxim := 0; for var i := 1 to length(s) do if s[i] in 'ABC' then begin k += 1; if k > maxim then maxim := k end else k := 0 ; write(maxim) end.
24 задание с сайта К. Полякова, № 26:
В текстовом файле k7a-6.txt находится цепочка из символов латинского алфавита A, B, C, D, E, F.
Найдите длину самой длинной подцепочки, не содержащей гласных букв.
Ответ: 20
begin assign(input, 'k7a-6.txt'); var s: string; read(s); var k := 0; var maxim := 0; for var i := 1 to length(s) do if s[i] in 'BCDF' then begin k += 1; if k > maxim then maxim := k end else k := 0 ; write(maxim) end.
begin var s := readAllText('d:\k7a-6.txt').Trim; var (k, max) := (0, 0); foreach var c in s do if not (c in 'AE') then begin k += 1; if k > max then max := k; end else k := 0; print(max) end.
24 задание с сайта К. Полякова, № 27:
В текстовом файле k7b-1.txt находится цепочка из символов латинского алфавита A, B, C, D, E.
begin assign(input, 'k7b-1.txt'); var s: string; read(s); var c := 'EAB'; while c in s do begin if c[length(c)] = 'B' then c += 'E' else if c[length(c)] = 'A' then c += 'B' else if c[length(c)] = 'E' then c += 'A'; end; print(length(c) - 1) end.
Постоянно повторяется фрагмент EAB, поэтому возможны 3 варианта окончания строки:f=open('k7b-1.txt') s = f.readline() m = 0 i = 0 for char in s: if (char == 'E' and i%3 == 0) or \ (char == 'A' and i%3 == 1) or \ (char == 'B'and i%3 == 2): i += 1 m = max(i,m) elif char == 'E': i = 1 else: i = 0 print(m)
24 задание с сайта К. Полякова, № 33:
В текстовом файле k7c-1.txt находится цепочка из символов латинского алфавита A, B, C, D, E.
Найдите количество цепочек длины 3, удовлетворяющих следующим условиям:
Ответ: 1280
begin assign(input, 'k7c-1.txt'); var s: string; read(s); // весь текст файла var k := 0; var c1 := 'BCD'; var c2 := 'BDE'; var c3 := 'BCE'; for var i := 1 to length(s) - 2 do begin if (s[i] in c1) and (s[i + 1] in c2) and (s[i + 2] in c3) and (s[i] <> s[i + 1]) and (s[i + 1] <> s[i + 2]) then k += 1 end; print(k) end.
24 задание с сайта К. Полякова, № 52:
Ответ: 2 3
Видеоразбор:
24 задание с сайта К. Полякова, № 108:
Текстовый файл 24.txt содержит последовательность из строчных и заглавных букв английского алфавита и цифр, всего не более 10 6 символов. Определите длину наибольшей убывающей подпоследовательности.
Ответ: 3
for var i := 2 to length(s) do begin if s[i] < s[i - 1] then
. if k > max then max := k;
begin assign(input, 'D:/24.txt'); var s: string; read(s); // весь текст файла var k := 1; //длина текущей бывающей последовательности символов var max := 0; // макс длина for var i := 2 to length(s) do begin if s[i] < s[i - 1] then begin k += 1; // увеличиваем счетчик длины последовательности if k > max then max := k; end else k := 1; // сбрасываем счетчик для работы со след. последовательностью end; print(max) end.
Работа с числами (цифрами) в текстовом файле
24 задание с сайта К. Полякова, № 87:
Текстовый файл 24-1.txt состоит не более чем из 10 6 символов. Определите максимальное нечётное число, записанное в этом файле.
Ответ: 7642289
begin assign(input, '24-1.txt'); var s: string; var b:integer; read(s); // весь текст файла находится в s var max := 0; // для максимального нечётного числа var num:integer; var strnum:string; // накапливает строковое представление числа strnum:=''; for var i := 1 to length(s)-1 do begin if s[i].IsDigit() then // проверяем очередной символ - цифра ли это strnum += s[i] //добавляем очередную цифру в число else if (strnum <> '') then //если встретилась не цифра, а strnum не пустая строка begin Val(strnum, num, b); // переводим в число if (num mod 2 <> 0) and (num > max) then // условие для поиска макс четного max := num; strnum:=''; // сбрасываем на начальное значение, чтобы накапливать новое число end; end; // проверка на случай, если самое большое нечётное в самом конце строки if (s[length(s)].isdigit()) then begin Val(strnum, num, b); if (num mod 2 <> 0) and (num > max) then max:= num; end; print(max) end.
Работа с отдельными строками файла
24 задание с сайта К. Полякова, № 137:
Текстовый файл 24-s1.txt состоит не более чем из 10 6 заглавных латинских букв ( A..Z ). Текст разбит на строки различной длины.
Определите количество строк, в которых буква J встречается чаще, чем буква E .
Ответ: 482
begin assign(input, '24-s1.txt'); var s: string; var k := 0; while true do // бесконечный цикл begin readln(s); // считываем очередную строку if s = '' then break; // если строка пустая (т.е. достигнут конец файла), выходим if s.Count(c -> c = 'J') > s.Count(c -> c = 'E') then k += 1; end; print(k) end.
Рубрики:
Yatogami
Текстовый файл 24-173.txt состоит не более чем из 10 6 символов и содержит только заглавные буквы латинского алфавита (ABC…Z). Найдите максимальную длину подстроки, в которой ни одна тройка символов не записана два раза подряд. Например, в искомой подстроке не может быть фрагмента ABCABC
Можете помочь написать код
__________________Помощь в написании контрольных, курсовых и дипломных работ здесь
Не понимаю какой написать код для этой задачи
Помогите решить кому не трудно Известны результаты 2-х футбольных матчей между 2-мя командами.
Какой написать код для прокрутки музыки с помощью slider
Здравствуйте! Какой написать код для прокрутки музыки на вб 6.0? С помощью slider?
Какой код написать для выхода из функции, при истинном условии
Здравствуйте. У меня тут по книге задание, написать рекурсивную функцию, выводящую содержимое.
Какой код нужно написать в IBconsole, чтобы создать хранимые процедуры
Какой код нужно написать в IBconsole, чтобы создать хранимые процедуры: - по коду клиента вывести.
Какой написать код на динамических страницах для уникальных описаний страниц
Подскажите плиз. Есть база данных на сайте Есть страница документация, где формируется список.
Как добавить картинку и ссылку в файл xml! Какой код написать?
Какой код и вообще способ используется для вставки картинки в код файла xml? Также какой.
какой код нужно написать в БД, чтобы осужествить поиск по БД, созданной через майкроссофт аксесс
создала БД через аксесс, ФИО, адрес, телефон, вопрос: как осуществить поиск по БД, например, поиск.
Заменить одну подстроку в си на другую.Не знаю,какой код надо написать функцию replace с использованием strcat
Напечатать текст, заменив все подстроки bomb на watermelonНе знаю,какой код надо написать в функции.
Написать программу, которая определяет, на какой неделе и в какой день проходит урок из заданным номером N.
Помогите, пожалуйста, решить задачу. В первом полугодии учебного года занятия проходят с 1 по.
ЕГЭ информатика 24 задание разбор, теория, как решать.
Создание программы для обработки символьной информации, (В) — 1 балл
Е24.25 среди которых не более одной буквы A.
Текстовый файл содержит только заглавные буквы латинского алфавита (ABC…Z). Определите максимальное количество идущих подряд символов, среди которых не более одной буквы A. Ответ: 24.TXT СтатГрад Вариант ИН2110101 27.10.2021– задание №24
Е24.24 среди которых нет идущих подряд символов P
Текстовый файл состоит из символов P, Q, R и S. Определите максимальное количество идущих подряд символов в прилагаемом файле, среди которых нет идущих подряд символов P. Для выполнения этого задания следует написать программу. Ответ: 24.TXT Демонстрационный вариант ЕГЭ 2022 г. – задание №24
Е24.23 Определите, какая буква встречается в этой строке чаще всего
Е24.22 Найдите длину самой длинной подцепочки, состоящей из одинаковых символов.
Е24.21 непересекающиеся комбинации из 10 подряд стоящих букв X
Е24.20 Определите сколько раз встречаются непересекающиеся комбинации «XYZ» и «ZYX»
Определите сколько раз встречаются непересекающиеся комбинации «XYZ» и «ZYX». Текстовый файл состоит не более чем из 106 символов X, Y и Z. Для выполнения этого задания следует написать программу. Ниже приведён файл, который необходимо обработать с помощью данного алгоритма. Ответ: TXT Источник: «22.03.2021 ЕГЭ 100БАЛЛОВ, Иосиф Дзеранов»
Е24.19. Сколько раз встречается комбинация «OCK», не являющаяся при этом
Сколько раз встречается комбинация «OCK», не являющаяся при этом частью комбинации «STOCK». Текстовый файл состоит не более чем из 106 символов S, T, O, C, K. TXT Источник: «Евгений Джобс»
Е24.18. Сколько раз встречаются комбинации «BOSS» при этом
Сколько раз встречаются комбинации «BOSS» при этом до и после этого слова нет символа «J». Например, комбинации «JBOSS», «BOSSJ» и «JBOSSJ» не должны учитываться. Текстовый файл состоит не более чем из 106 символов J, O, B, S. TXT Источник: «Евгений Джобс»
Е24.17. Сколько раз встречаются комбинации «TIK» и «TOK»
Сколько раз встречаются комбинации «TIK» и «TOK». Текстовый файл состоит не более чем из 106 символов I, K, O, T. TXT Источник: «Евгений Джобс»
Е24.16. Определите максимальное количество подряд идущих одинаковых букв.
Определите максимальное количество подряд идущих одинаковых букв. Текстовый файл состоит не более чем из 106 символов F, A, I, L. TXT Источник: «Евгений Джобс»
Читайте также: