Входной файл: code.in Выходной файл: code.out Время на тест: 2 секунды Ограничение на память: 64MB Тесты к задаче:Скачать
Компания Racine Business Networks (RBN) подала в суд на компанию Heuristic Algorithm Languages (HAL), утверждая что HAL использовала исходный код из RBN UNIXÔ и внесла его в открытый код операционной системы HALinux.
Как RBN, так и HAL используют язык программирования, в котором каждый оператор располагается на отдельной строке и имеет вид:
STOREA = STOREB + STOREC
(STOREA, STOREB и STOREC — имена переменных). Каждый оператор записывается следующим образом: имя первой переменной начинается с первой позиции строки, затем — пробел, знак равенства, пробел, имя второй переменной, пробел, знак сложения, пробел и имя третьей переменной. Одно и то же имя переменной может встречаться в строке более одного раза. Имена переменных имеют длину от 1 до 8 символов и состоят из заглавных латинских ASCII букв (‘A’…’Z’).
Утверждается, что HAL скопировала последовательность строк программы прямо из исходного кода RBN с минимальными изменениями.
Чтобы скрыть свое преступление, HAL изменила имена некоторых переменных. Точнее, HAL взяла последовательность строк из программы RBN и для каждой переменной в ней изменила ее имя. При этом новое имя переменной может совпасть со старым. После переименования никакие две различные переменные не могут называться одинаково.
HAL могла изменить в некоторых строках порядок имен переменных в правой части оператора присваивания. Например, оператор вида
STOREA = STOREB + STOREC
мог быть изменен так:
STOREA = STOREC + STOREB
Утверждается также, что HAL не изменила порядок, в котором строки кода следуют в исходном тексте программы.
Необходимо по заданным исходным кодам программ RBN и HAL найти самую длинную последовательность подряд идущих строк из программы HAL, которую можно получить из последовательности подряд идущих строк программы RBN с помощью указанных выше преобразований. Заметьте, что найденная последовательность в коде HAL и соответствующая ей последовательность в коде RBN не обязательно начинаются в строках с одинаковыми номерами.
Входные данные: code.in
Первая строка входного файла содержит два разделенных пробелами целых числа R и H (1 £ R £ 1000; 1 £ H £ 1000). R задает число строк в коде программы RBN, а H — число строк в коде программы HAL.
Последующие R строк содержат программу RBN.
Последующие H строк содержат программу HAL.
Пример входных данных:
4 3
RA = RB + RC
RC = D + RE
RF = RF + RJ
RE = RF + RF
HD = HE + HF
HM = HN + D
HN = HA + HB
Выходные данные: code.out
Выходной файл должен содержать одну строку с единственным целым числом — длиной самой длинной последовательности идущих подряд строк, которую HAL могла скопировать с изменениями у RBN.
Пример выходных данных:
2
Строки с 1-й по 2-ю из программы RBN совпадают со строками со 2-й по 3-ю из программы HAL при условии, что в программе RBN выполнены следующие замены имен переменных: RA ® HM, RB ® D, RC ® HN, D ® HA, RE ® HB. Решения с тремя и более соответствующими строками не существует.