eolymp
bolt
Try our new interface for solving problems
Məsələlər

Мутация

Мутация

Ученые планеты Олимпия впритык приблизились к открытию характерного генома для вида олимпийских амеб, а именно: они нашли последовательность генов, про которую известно, что она содержит ровно один лишний ген. На текущем этапе ученым необходимо найти все гены, которые могут оказаться лишними в этой последовательности. Для этого ученые используют геном организма, который гарантировано есть представителем этого вида. Последовательность генов, найденная учеными, и геном организма могут быть представлены в виде строки, составленной из маленьких букв английского алфавита. Каждая буква соответствует отдельному гену. Известно, что организм \textbf{A} принадлежит определенному виду \textbf{X}, если из строки, которая представляет геном организма \textbf{A}, можно вычеркнуть определенные символы и получить строку, которая представляет характерный геном для вида \textbf{X}. Напишите программу, которая по заданной последовательности генов, найденной учеными, и геному представителя вида, найдет индексы всех генов, которые могут буть лишними в последовательности генов найденной учеными. \InputFile Содержит две строки. Первая строка представляет найденную учеными последовательность генов. Вторая строка - геном представителя вида. Обе строки непустые, состоят из маленьких букв латинского алфавита, и длина каждой из них не превышает \textbf{40 000} символов. \OutputFile Первая строка должна содержать одно целое число - количество генов, каждый из которых, вероятно, является лишним в найденой учеными последовательности генов. Во второй строке выведите индексы всех таких генов в порядке возрастания. Гарантовано, что существует хотя бы один лишний ген. \textit{\textbf{Пояснение к примеру}}: Из последовательности \textbf{adca} нужно удалить либо ген \textbf{d}, либо ген \textbf{с}. Таким образом, в первом случае мы получим последовательность \textbf{aca}, которую можно получить из генома, например, так: \textbf{a}b\textbf{c}dab\textbf{a}, а во втором случае --- последовательность \textbf{ada}, которую можно получить, например, так: \textbf{a}bc\textbf{d}ab\textbf{a}.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
adca
abcdaba
Çıxış verilənləri #1
2
2 3
Müəllif Роман Едемский
Mənbə 2012 XXV All-Ukrainian Informatics Olympiad, Vinnitsa, March 24 - 28, Round 1