Задача - написать программу, которая по исходной и требуемой цепочкам ДНК будет находить необходимую для этого цепочку элементарных преобразований.
Технические условия
Входные данные
Первая строка входного файла содержит описание исходной цепочки ДНК, вторая строка - описание требуемой цепочки ДНК. Длины обеих цепочек совпадают и не превышают 5000. Каждая из цепочек содержит только символы из множества {A, G, C, T}.
Гарантируется, что искомая последовательность преобразований существует.
Выходные данные
В первой строке выходного файла выведите количество k преобразований в построенном решении. Число k должно быть неотрицательным и не должно превышать 4999.
Далее выведите k строк, описывающих построенную последовательность элементарных преобразований. Каждая из строк должна содержать два числа: li и ri - соответственно левый и правый конец разворачиваемого на i-м шаге отрезка.
Информация о задаче
Лимит времени: 1 секунда
Лимит памяти: 64 MB
Пример
Пример входных данных
Sample 1
AGCT
GCAT
Sample 2
AGCTA
ATCGA Пример выходных данных
Sample 1
2
1 2
2 3
Sample 2
1
1 5
Технические условия
Входные данные
Первая строка входного файла содержит описание исходной цепочки ДНК, вторая строка - описание требуемой цепочки ДНК. Длины обеих цепочек совпадают и не превышают 5000. Каждая из цепочек содержит только символы из множества {A, G, C, T}.
Гарантируется, что искомая последовательность преобразований существует.
Выходные данные
В первой строке выходного файла выведите количество k преобразований в построенном решении. Число k должно быть неотрицательным и не должно превышать 4999.
Далее выведите k строк, описывающих построенную последовательность элементарных преобразований. Каждая из строк должна содержать два числа: li и ri - соответственно левый и правый конец разворачиваемого на i-м шаге отрезка.
Информация о задаче
Лимит времени: 1 секунда
Лимит памяти: 64 MB
Пример
Пример входных данных
Sample 1
AGCT
GCAT
Sample 2
AGCTA
ATCGA Пример выходных данных
Sample 1
2
1 2
2 3
Sample 2
1
1 5