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.
Имеется текст и N слов. Длина текста составляет L символов,
длина каждого слова — от 1 до 255 символов.
Требуется для каждого слова определить, входит ли оно в текст.
Все слова и текст состоят из латинских букв. Заглавные и строчные буквы считаются различными.
Обратите внимание, данная задача отличается от задачи B только ограничениями.
Формат входного файла
В первой строке входного файла содержится текст,
во второй — число N, в следующих N строках — слова.
Формат выходного файла
В выходном файле должны содержаться N чисел 1 или 0,
обозначающих, что соответствующее слово входит или не входит в текст.
Будем говорить, что строки a и bимеют k различий, если длины этих строк
одинаковы, а символы в позициях с одинаковыми номерами совпадают все, кроме k штук.
Например, строки ABABAC и BBABAB имеют 2 различия.
По данной строке S длиной N символов и числу k требуется
найти две подстроки одинаковой длины, начинающиеся с различных позиций,
и имеющие не более k различий.
Формат входного файла
Входной файл содержит в первой строке целое число k, в во второй — строку S.
Формат выходного файла
Выходной файл должен содержать целое число — длину самой длинной найденной подстроки,
либо 0 (ноль), если решения не существует.
Абзац текста состоит из n слов длиной l1,
l2, ..., ln (длина слова - число символов
в нем). Требуется оптимальным образом разбить его на строки длиной не более
M символов. Оптимальность при этом определяется так: посчитаем число
"лишних" пробелов в каждой строке и сложим кубы этих чисел для всех строк,
кроме последней. Чем больше эта сумма (назовем ее оценочной суммой),
тем хуже абзац.
Формат входного файла
В первой строке находятся числа n и M. Далее следует
n чисел li.
Формат выходного файла
Выходной файл должен содержать единственное число - значение оценочной суммы
абзаца при оптимальном разбиении на строки.
