00. Материалы курса "Обработка строк" ≡

Пререквизиты

Онлайн-курс "Основы C/C++ для спортивного программирования"

Онлайн-курс "Быстрый старт в спортивное программирование"

Видеозапись лекций курса "Введение в алгоритмы" ДВФУ

Видеозапись лекций курса "Язык Питон" ДВФУ

Практические задания курса "Язык Питон" ДВФУ

Основной материал

Справочник по алгоритмам: Викиконспекты

Видеозапись лекций

Задача 01A. Подсчёт слов ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

This       is  a  test	

4

Qqqqqqqqqq

1

Задача 01B. Короткий текст и немного слов ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

Longlongstring
2
short
string

0 1

Задача 02A. Количество слов ≡

Условие

Во входном файле записана строка текста, в которой могут встречаться:

• прописные и строчные (т.е. большие и маленькие) латинские буквы,
• пробелы,
• знаки препинания: точка, запятая, восклицательный и вопросительный знак,
• символ -, обозначающий в некоторых случаях тире, а в некоторых — дефис.

Слово — это последовательность подряд идущих латинских букв и знаков дефис, ограниченная с обоих концов. В качестве ограничителей могут выступать начало строки, конец строки, пробел, знак препинания, тире. Тире отличается от дефиса тем, что слева и справа от знака дефис пишутся буквы, а хотя бы с одной стороны от тире идет либо начало строки, либо конец строки, либо пробел, либо какой-либо знак препинания, либо еще одно тире.

Напишите программу, определяющую, сколько слов в данной строке текста.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

Hello , world!

2

www.olympiads.ru

3

Gyro-compass - this is a ...

4

Задача 02B. Форматированные строки ≡

Условие

Пусть имеются две строки, содержащие набор слов, состоящих из цифр и символов латинского алфавита, и отделенных друг от друга пробелами либо знаками препинания ('-', '.', ',', ':', ';', '!', '?'). Регистр символов, а также количество подряд идущих пробелов роли не играет (любое число пробелов воспринимается как один символ). Пробелы, расположенные по краям строки либо отделяющие знаки препинания, игнорируются.

Для определения формата текста в пределах каждой такой строки используются теги следующих видов:

<b>текст</b> — жирный шрифт;

<i>текст</i> — курсив.

Также допускается использование нескольких вложенных друг в друга тегов. При этом внутренний тег сохраняет форматирование внешнего фрагмента.

Теги могут разбивать слово на части: <i><b>тек</b>ст</i>. В этом случае, отдельные части слова будут иметь различное форматирование.

В свою очередь, на пробельные символы форматирование не распространяется.

Требуется сравнить две такие строки.

Формат входного файла

Во входном файле "input.txt" содержатся две строки, между которыми необходимо выполнить сравнение.

Формат выходного файла

Выходной файл "output.txt" должен содержать одно из следующих значений:

2 — текст в обеих строках совпадает и имеет одинаковый формат;

1 — текст в обеих строках совпадает, но имеет разный формат;

0 — обе строки содержат разный текст.

Ограничения

Полагается, что в исходных строках отсутствуют синтаксические ошибки,
связанные с порядком расстановки тегов.

Длина каждой строки не превосходит 3 ⋅ 10⁶.

Примеры тестов

<i>THIS </i><i>IS   <b>SPARTA!!!</b></i>
<i>this   is    <b>Sparta  ! !!</b></i>

2

<i>THIS IS   <b>SPARTA!!!</b></i>
<i>this is</i> <b>Sparta!!!</b>

1

<i>THIS IS   <b>SPARTA!!!</b></i>
<i>This Is   <b>Sparta!</b></i>

0

Задача 02C. Радуга ≡

Условие

Требуется написать программу, которая печатает все цвета радуги на русском языке. Каждый цвет вывести в отдельной строке с большой буквы.

Цвета должны быть выведены в кодировке WINDOWS-1251.

Примеры тестов

Красный
Оранжевый
Желтый
Зеленый
Голубой
Синий
Фиолетовый

Задача 03A. Число вхождений подстроки ≡

Условие

Пусть имеется текстовая строка S, состоящая из произвольных печатных символов (ASCII 32-126). Требуется определить общее число ее подстрок, совпадающих с некоторым заданным образцом T.

Для решения задачи следует воспользоваться алгоритмом Кнута-Морриса-Пратта.

Формат входного файла

В заголовке входного файла "input.txt" содержится строка T, выступающая в роли образца. Далее следует строка S, в которой необходимо выполнить поиск.

Формат выходного файла

Выходной файл "output.txt" должен содержать число найденных подстрок.

Ограничения

0 < |T| ≤ 5 ⋅ 10⁴, 0 ≤ |S| ≤ 2 ⋅ 10⁷

Примеры тестов

ABCDEF
123 AB ABCDEFABCDEF ABCDEF45ABCDEFuZ

4

ABCABC
ZEt AB ABCABCABCABC ABC45-ABCABCABC+

5

Задача 03B. Сравнения подстрок ≡

Условие

Дана строка. Нужно уметь отвечать на запросы вида: равны ли подстроки [a… b] и [c… d].

Формат входных данных

Сперва строка S из строчных латинских букв. Далее число M — количество запросов.

В следующих M строках по четыре целых числа — запросы a, b, c, d.

Формат выходных данных

Выведите M строк, по одному ответу для каждого запроса. Ответ должен быть Yes, если подстроки совпадают, и No в противном случае.

Ограничения

0 ≤ M ≤ 10⁵, 1 ≤ a ≤ b ≤ |S|, 1 ≤ c ≤ d ≤ |S|, 1 ≤ |S| ≤ 10⁵.

Примеры тестов

trololo
3
1 7 1 7
3 5 5 7
1 1 1 5

Yes
Yes
No

Задача 03C. Неточные подстроки ≡

Условие

Будем говорить, что строки a и b имеют k различий, если длины этих строк одинаковы, а символы в позициях с одинаковыми номерами совпадают все, кроме k штук. Например, строки ABABAC и BBABAB имеют 2 различия.

По данной строке S длиной N символов и числу k требуется найти две подстроки одинаковой длины, начинающиеся с различных позиций, и имеющие не более k различий.

Формат входного файла

Входной файл содержит в первой строке целое число k, в во второй — строку S.

Формат выходного файла

Выходной файл должен содержать целое число — длину самой длинной найденной подстроки, либо 0 (ноль), если решения не существует.

Ограничения

Строка S состоит из заглавных латинских букв.

0 ≤ k ≤ N ≤ 1000

Примеры тестов

1 
A

0

2
ABCACB

3

Задача 04A. Наибольшая общая подстрока ≡

Условие

Найдите наибольшую общую подстроку строк s и t.

Формат входного файла

Первая строка входного файла содержит строку s, вторая — t (1 ≤ |s|, |t| ≤ 100,000). Строки состоят из строчных латинских букв.

Формат выходного файла

Выведите одну строку — наибольшую общую подстроку строк s и t. В случае, если ответ не единственный, выведите минимальный лексикографически.

Ограничения

Примеры тестов

ababb
abacabba

aba

Задача 04B. Расстояние Левенштейна ≡

Условие

Расстояние Левенштейна (также редакционное расстояние или дистанция редактирования) между двумя строками — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.

Даны два слова. Необходимо вычислить расстояние Левенштейна между ними.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

aaaa
bbbb

4

abc
aabb

2

Задача 04C. Минимальное расстояние Левенштейна ≡

Условие

Дано N строк, состоящих из заглавных латинских букв (аминокислот). Требуется написать программу, определяющую пару строк с наименьшим расстоянием Левенштейна, включающего вставки, удаления и замены символов. Вес замены равен 2, вес вставки и удаления равен 1.

Формат входного файла

Во входном файле содержатся N строк.

Формат выходного файла

Выходной файл должен содержать три целых числа — два различных номера строк, расстояние между которыми наименьшее, и само расстояние. Строки нумеруются от 1 до N.

Ограничения

N = 25. Длина строк не превосходит 1000 символов. Если существует несколько решений, выведите c минимальным N, минимизировать сначала первый номер, потом второй. Например 1 10, а не 2 9.

Примеры тестов

D
PN
LAD
S
RA
NP
AS
A
GPW
EGA
AQ
KY
FKG
GA
N
GPVSLGGLP
YR
G
PEAGPMISK
KGNN
GG
GPWM
NS
AGP
TDQNGG

2 15 1

Задача 04D. Выравнивание строк ≡

Условие

Вам даны:

• Числа D, E — штрафы за начало нового разрыва в выравнивании строк и штраф за его продолжение соответственно.

• Алфавит символов в виде строки A, состоящей из заглавных латинских букв.

• Матрица замен символов R, соответствующая стоимости сопоставления каждой пары символов при выравнивании строк. Строки и столбцы матрицы соответствуют символам алфавита в том порядке, в котором они указаны в строке A

• Две строки P и Q.

Требуется найти выравнивание строк P и Q, максимизирующее функцию стоимости данного выравнивания.

Выравнивание двух строк это также пара строк (Q₁, Q₂) одинаковой длины L, состоящих из символов алфавита, и символа "-", означающего разрыв.

Стоимость выравнивания S вычисляется по формуле: S(Q₁, Q₂) = ∑L − 1i = 0f(Q₁[i], Q₂[i]),

где f(Q₁[i], Q₂[i]) = D, если выполнено хотя бы одно из условий

• Q₁[i] равен "-", а Q₁[i − 1] не равен "-"
• Q₂[i] равен "-", а Q₂[i − 1] не равен "-"

f(Q₁[i], Q₂[i]) = E, если выполнено хотя бы одно из условий

• Q₁[i] равен "-", и Q₁[i − 1] равен "-"
• Q₂[i] равен "-", и Q₂[i − 1] равен "-"

Иначе f(Q₁[i], Q₂[i]) = R[Q₁[i]][Q₂[i]]

Формат входных данных

Первая строка содержит целые числа D, E.

Вторая строка содержит строку-алфавит A.

Далее |A| строк содержат по |A| целых чисел — элементы матрицы R.

Последние две строки содержат строки P и Q.

Формат выходных данных

В первой строке выходного файла выведите стоимость выравнивания.

В последующих двух строках выведите выравнивание.

Если оптимальных решений несколько, выведите любое из них.

Ограничения

|D, E| ≤ 1000

 − 10 ≤ R_ij ≤ 10

Длина строк не превосходит 500. Строки состоят только из символов алфавита и не могут быть пустыми.

Примеры тестов

-5 -1
AGCT
1 -1 -1 -1 
-1 1 -1 -1
-1 -1 1 -1
-1 -1 -1 1
GAAAAAAT
GAAT

-4
GAAAAAAT
G----AAT

0 -1
AGCT
1 -1 -1 -1 
-1 1 -1 -1
-1 -1 1 -1
-1 -1 -1 1
GAAAAAAT
GAAT

3
GAAAAAAT
G-A-A--T

-4 -5
AGCT
10 -1 -3 -4
-1 7 -5 -3
-3 -5 9 0
-4 -3 0 8
AGACTAGTTAC
CGAGACGT

20
--AGACTAGTTAC
CGAGAC--G-T--

-18 -5
AGCT
10 -1 -3 -4
-1 7 -5 -3
-3 -5 9 0
-4 -3 0 8
AGACTAGTTAC
CGAGACGT

-10
AGACTAGTTAC
---CGAGACGT

Задача 05A. Длинный текст и много слов (revisited) ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

longlongstring
2
short
string

0 1

Задача 05B. Префиксные основы ≡

Условие

Пусть имеется формальный язык, слова которого представляют собой цепочки символов, составленные из отдельных неперекрывающихся подцепочек (морфов). Значения, которые способны принимать указанные морфы, образуют словарь базовых единиц (основ) исходного языка. При этом полагается, что никакие две основы не могут иметь общих префиксов.

Для заданного набора слов требуется определить список основ, разбивающих их на минимально возможное число морфов. Для каждой такой основы необходимо также посчитать, сколько раз она встречается в исходном тексте (в качестве значения какого-либо морфа).

Формат входного файла

В начале входного файла "input.txt" хранится натуральное число n. Далее следует набор из n слов, состоящих из цифр и букв латинского алфавита (регистр их написания неважен). При этом каждое слово располагается в отдельной строке.

Формат выходного файла

Выходной файл "output.txt" должен содержать все найденные основы (без повторений), приведенные к одному регистру и расположенные в лексикографическом порядке. Напротив каждой такой основы (через пробел) указывается число совпадающих с ней морфов.

Ограничения

Полагается, что длина отдельно взятого слова лежит в диапазоне от 1 до 5000.

0 < n ≤ 10⁵.

Размер входного файла не превосходит 10 МБ.

Примеры тестов

10
abcd11112345
y4141
abcd1111
abcdy
yyyy
abcdabcdabcd
A1111
A1111
11114141
AbcD

1111 5
2345 1
4141 2
a 9
bcd 7
y 6

10
111123abcd
y4141A
abcd1111
y4141a
abcdy
AbCdA
AbCd1111
abcd
A1111
aA

1111 4
23abcd 1
4141a 2
a 9
bcd 5
y 3

Задача 05C. Сжатый префиксный словарь ≡

Условие

Пусть имеется текстовая строка S, состоящая из цифр и букв латинского алфавита. При этом полагается, что регистр их написания неважен, т.е. заглавные и строчные символы эквивалентны между собой. На основе указанной строки требуется сформировать словарь T, в котором отдельным ее подстрокам ставятся в соответствие некоторые числовые коды. Описание вычислительной процедуры для получения таких кодов приводится ниже:

1. на начальном этапе алгоритма создадим пустой словарь T и заведем счетчик k = 0;
2. будем двигаться по заданной строке, читая ее символы слева направо;
3. находясь в начале очередного суффикса строки S, выберем наименьший непустой его префикс, который отсутствует в словаре T;
4. выбранный на предыдущем этапе префикс добавим в словарь, указав в качестве числового кода его порядковый номер k;
5. увеличим счетчик k на единицу;
6. дальнейший поиск продолжается с позиции, следующей после указанного префикса.

Если при попытке добавления очередной подстроки число записей в словаре превысит некоторое заданное n, словарь должен быть очищен. Счетчик k при этом обнуляется. Последний считанный символ (в окончании текущего префикса) возвращается в поток, и процедура возобновляется с той же позиции, в которой она остановилась.

В качестве ответа требуется вывести содержимое такого словаря на момент окончания входной строки.

Формат входного файла

В первой строке входного файла "input.txt" записано натуральное число n.
Далее следует строка S, для которой необходимо построить словарь.

Формат выходного файла

В выходной файл "output.txt" нужно вывести все содержащиеся в словаре подстроки, приведенные к одному регистру и расположенные в лексикографическом порядке.
Напротив каждой такой строки (через пробел) следует указать ее порядковый номер.

Ограничения

10 ≤ n ≤ 5000, 0 < |S| ≤ 2 ⋅ 10⁷

Примеры тестов

50
BaNaNAbaNAnaBaNaNAba

a 1
ab 4
aba 9
an 3
ana 5
b 0
ba 7
n 2
na 6
nan 8

10
12uitNp3zxrv45swe6qa

4 2
5 3
6 7
a 9
e 6
q 8
r 0
s 4
v 1
w 5

Задача 05D. Вывод сжатого суффиксного дерева ≡

Условие

Сжатое суффиксное дерево, построенное по алгоритму Укконена, в каждом своем ребре хранит информацию о символах которые там находятся, а именно (первый символ, глубина*, индекс первого символа ребра, индекс последнего символа ребра)

Требуется найти все ребра, находящееся на глубине D.

Вывод требуется выполнять по аналогии с алгоритмом поиск в глубину, то есть вывод выполняется из корня к листьям

Формат входных данных

Входной файл содержит строку длины D из которой было построено дерево и глубину l

Формат выходных данных

Программа должна вывести поочередно все ребра с их параметрами. Каждое ребро записывается с новой строки, все индексы берутся из соответствующих символов в исходной строке.

Алгоритм Укконена подразумевает наличие конечного символа в строке, но в данной задаче при выводе ребер этот символ не должен встречаться

*Глубина - расстояние ребра от корня дерева (изначально равна 0).

Ограничения

0 ≤ S ≤ 100000

1 ≤ D ≤ 5

Примеры тестов

abcd 1

$ 1 4 4
a 1 0 4
b 1 1 4
c 1 2 4
d 1 3 4

abcabxabcd 2

c 2 2 2
x 2 5 10
c 2 2 2
x 2 5 10
a 2 3 10
d 2 9 10

Задача 06A. Укорачивание текста ≡

Условие

По заданному тексту длины N и образцу длины K определить длину минимальной подстроки в тексте, которая удовлетворяет данному образцу. Текст состоит только из маленьких латинских букв. Образец содержит маленькие латинские буквы и символ '*', заменяющий любое множество любых символов(в том числе пустое).

Формат входного файла

Формат выходного файла

В выходном файле должно находится единственное число — минимальная длина искомой подстроки, или  − 1, если образец в тексте не встречается.

Ограничения

Примеры тестов

3 4
a*b
abab

2

Задача 06B. Целые числа на Паскале ≡

Условие

Требуется написать программу, которая принимает на вход строку, определяет, является ли она записью знакового целого числа на языке Free Pascal, и если да, то каково значение этого числа.

Формат входных данных

Входные данные содержат одну строку.

Формат выходных данных

Первая строка выходных данных должна содержать число:

• 0 — если входная строка является корректной записью знакового целого числа, входящего в допустимый диапазон для типа Longint.
• 1 — если входная строка не является корректной записью знакового целого числа,
• 2 — если входная строка является корректной записью знакового целого числа, НЕ входящего в допустимый диапазон для типа Longint.

Если первая строка содержит 0, во второй строке должно содержаться значение числа в десятичной записи.

Ограничения

Длина входной строки не более 100 символов.

Примеры тестов

$A

0
10

--

1

9999999999999999999999999

2