Problem A. Knuth-Morris-Pratt

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

You are to write a program that receives two strings and finds position where the second string appears in the first one as a substring.

Input file format

First and second lines of input file contain given strings. Each string is a sequence of lower-case Latin letters from 'a' to 'z' and spaces.

Output file format

Output file must contain a single integer — position of the first occurrence of the substring in a string, or  − 1 if there is none. Positions are numbered from 1.

Constraints

Length of each string does not exceed 100000 characters.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
yezhiki nachinayut i vyygryvayut
yut
16

Задача B. Длинный текст и много слов

Автор:A. Klenin   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

Имеется текст и N слов. Длина текста составляет L символов, длина каждого слова — от 1 до 255 символов. Требуется для каждого слова определить, входит ли оно в текст. Все слова и текст состоят из латинских букв. Заглавные и строчные буквы считаются различными. Обратите внимание, данная задача отличается от задачи B только ограничениями.

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

В первой строке входного файла содержится текст, во второй — число N, в следующих N строках — слова.

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

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

Ограничения

1 ≤ L ≤ 20000, 1 ≤ N ≤ 10000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
Longlongstring
2
short
string
0 1

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

Автор:А. Кленин   Ограничение времени:4 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

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

0 ≤ k ≤ N ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 
A
0
2
2
ABCACB
3

Задача D. Разбиение абзаца на строки

Автор:Т. Кормен, Ч. Лейзерсон, Р. Ривест, Т. Чистяков   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

Абзац текста состоит из n слов длиной l1, l2, ..., ln (длина слова - число символов в нем). Требуется оптимальным образом разбить его на строки длиной не более M символов. Оптимальность при этом определяется так: посчитаем число "лишних" пробелов в каждой строке и сложим кубы этих чисел для всех строк, кроме последней. Чем больше эта сумма (назовем ее оценочной суммой), тем хуже абзац.

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

В первой строке находятся числа n и M. Далее следует n чисел li.

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

Выходной файл должен содержать единственное число - значение оценочной суммы абзаца при оптимальном разбиении на строки.

Ограничения

1 <= n <= 10000, 1 <= M <= 100000, 1 <= li <= M

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 6 
2 1 2 5
72

0.227s 0.009s 19