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

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

Условие

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

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

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

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

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

Ограничения

1 ≤ N ≤ 1000000, 1 ≤ K ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 4
a*b
abab
2

Problem B. 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

0.169s 0.012s 15