- Описание
- Отправленные решения
16. Опечатки
(эпиграф)(с одного форума)
— Кто сочинил эту чушь?
— Астрофизики. Они тоже люди.
— Вы 10 ошибок в слове журналисты сделали.
Многие пользователи делают ошибки при наборе, некоторые — из-за попаданий мимо клавиш, некоторые — из-за своей неграмотности. Мы хотим проверить, мог ли пользователь на самом деле иметь в виду некоторое другое слово, чем то, которое он набрал.
Более формально, предположим, что имеет место следующая модель ошибок: пользователь начинает с некоторого слова, которое он хочет написать, и дальше последовательно делает в нём некоторое количество ошибок.
Каждая ошибка представляет собой замену некоторой подстроки слова на другую подстроку.
Одно ошибка соответствует замене только в одной позиции (то есть если пользователь захочет сделать единственную ошибку по правилу abc -> cba, то из строки abcabc он может получить либо cbaabc, либо abccba.
После каждой ошибки процесс повторяется.
Одно и то же правило могло использоваться несколько раз в различных шагах (так, в вышеприведённом примере за два шага могло получиться cbacba).
Требуется определить, какое минимальное количество ошибок пользователь мог совершить, если он имел в виду одно заданное слово, а написал — другое.
Формат ввода
В первой строке содержится слово, которое по нашему предположению пользователь имел в виду (оно состоит из букв латинского алфавита в нижнем регистре, длина не превышает 20).
Во второй строке содержится слово, которое он на самом деле написал (оно также состоит из букв латинского алфавита в нижнем регистре, длина не превышает 20).
В третьей строке содержится единственное число $N$ ($N \le 50$) — количество замен, описывающих различные ошибки.
В следующих $N$ строках содержатся возможные замены в формате
<правильная последовательность букв><пробел><ошибочная последовательность букв>.
Последовательности имеют длину не более 6 символов.
Формат вывода
Требуется вывести одно число — минимальное количество ошибок, которое мог совершить пользователь. Если это количество превышает 4, или же из одного слова невозможно получить другое, следует вывести -1.
Ограничения
Ограничение времени
5 с
Ограничение памяти
64 МБ
Пример 1
mlax
drum
50
l r
mlax gtwt
m d
mlax ujoc
ml pq
m f
ml bf
mlax aruq
mlax nqdd
mlax fglm
mlax bfit
mlax mziq
mla hlb
a u
mlax vmpa
m w
a w
ax ok
mla kqf
m e
x x
ml if
ml gk
l e
mla xrh
m j
a c
a b
m q
ax fr
ml sb
mlax gxxx
x m
mlax hczx
l q
la sv
l g
ax eh
lax mjh
la ec
la pv
ml iq
a q
lax jrs
la qn
lax bjo
l o
a z
l n
a c4