Problem B. Banner scrolling ≡

Statement

Young web developer Vasya was hired by "Dalstolb" company. Company maintains a popular news website with many advertisement banners. Marketing department of "Dalstolb" has proposed a new idea for animated transition between two text messages on the banner.

Message is a single line of characters. First message has length L₁, second has length L₂ ≥ L₁. Since the banner width is only enough to fit L₁ characters, the message after the transition should contain any substring the second message of length L₁. Transition should be performed as a series of animation frames. Each frame, message is either scrolled to the right by removing leftmost character and appending arbitrary new character from the right, or scrolled to the left by removing rightmost character and appending arbitrary new character from the left.

You program must, given two messages, find a shortest possible transition between them.

Input file format

First line of the input file contains the first message. Second line of the input file contains the second message. Messages are composed of small Latin letters.

Output file format

First line of output file must contain integer N — minimum number of frames. Following N lines must contain two-character string each — frame descriptions. First character must be either L or R, denoting right or left scrolling correspondingly. Second character must be a small Latin letter which should be appended to the message.

Constraints

1 ≤ L₁ ≤ L₂ ≤ 2000;

Sample tests

acm
solutionaccepted

1
Ln

vvostoker
vladivostok

4
Rz
Li
Ld
La

Explanation

Обозначим данные в условии задачи строки за P и T, а их длины — за m и n соответственно. По условию, необходимо преобразовать P в некоторую подстроку T за минимальное количество действий.

Разрешается повторять одно из двух действий: сдвиг окна влево и сдвиг окна вправо. При сдвиге окна влево содержимое строки P сдвигается на 1 символ вправо, при этом последний символ исчезает, а на первую позицию можно поставить любой символ. Аналогичные действия происходят при сдвиге окна вправо.

Извлечём простые следствия из условия задачи.

Во-первых, при m > n решение невозможно, поскольку при этом условии в T просто не будет существовать подстрок длины m.

Во-вторых, если m ≤ n, то решение наоборот найдётся всегда. Действительно, достаточно взять любую подстроку T длиной m, например T[1..m], и за m правых (или левых) сдвигов превратить P в T[1..m], что полностью удовлетворяет условию задачи.

Почему такое тривиальное решение не всегда является оптимальным? Потому что в случае, если в T уже содержится подстрока, похожая на P, то может быть можно преобразовать P в эту подстроку за количество действий, меньшее чем m. Например, если в строке T строка P уже содержится как подстрока, то ответом будет 0. Таким образом, тот алгоритм, который мы должны составить, должен в частном случае находить подстроку в строке.

Предположим, что решение найдено и минимальное количество действий преобразует строку P в строку P′, которая является подстрокой T. Рассмотрим P и P′. Символы P′ делятся на те, которые исходно находились в P (но могут быть сдвинуты), и те, которые были добавлены при сдвигах. Рассмотрим второй пример. В нём P = "vvostoker", T = "vladivostok", P′ = "adiVOSTOK". Здесь заглавными буквами в P′ выделены те символы, которые первоначально находились в P. Как могут располагаться в P′ такие символы? В P′ не могут встретится две группы таких символов, поскольку тогда невозможно с помощью сдвигов изменить символы между этими группами. Например, если рассмотреть P′ = "adiVOxxOK", то чтобы поставить символы "xx" на своё место, необходимо удалить и восстановить или символы "VO" или "OK". Следовательно, в P′ символы из P могут образовать лишь одну группу.

Учитывая приведённые выше соображения, рассмотрим подзадачу.

Подзадача 1. Известна строка Q, которая одновременно является подстрокой в P и в T. Необходимо найти минимальное количество действий, которое преобразует P в подстроку T, при этом оставляя группу Q нетронутой.

Решение подзадачи 1. Обозначим |Q| = k, количество символов P слева от Q через l, количество символов справа от Q — через r. Таким образом, l + k + r = m. Одна из стратегий преобразования строки может заключаться в том, чтобы совершить l правых сдвигов, добавляя к P справа произвольные символы, а потом совершить l + r левых сдвигов, добавляя символы, которые предшествуют вхождению Q в T. Такая стратегия требует 2l + r действий. Симметричная стратегия требует l + 2r действий. А значит, в простом случае необходимо выбрать из двух указанных стратегий и потратить min(2l + r, l + 2r) = l + r + min(l, r) действий.

Рассмотрим во втором примере Q = "vostok". Здесь k = 6, l = 1, r = 2. Из двух упомянутых стратегий оптимальной является первая, которая требует в этом случае 2l + r = 4 действия. Последовательность преобразований при этом выглядит так: P = "vvostoker" −  > "vostokerz" −  > "ivostoker" −  > "divostoke" −  > "adivvostok" = P′.

Несложно понять, что стратегии, в которых левые и правые сдвиги чередуются, требуют больше действий. Однако, например, стратегия 1 требует, чтобы слева от вхождения Q в T располагалось не менее l + r символов. Аналогично, стратегия 2 требует не менее l + r символов справа от вхождения Q. Если же символов для применения стратегии недостаточно, потребуется чередовать левые и правые сдвиги, и выбрать из двух стратегий более удачную. Мы предлагаем читателю проделать это в качестве упражнения.

Общее решение задачи. Умея решать подзадачу 1 необходимо перебрать все подстроки P, которые являются одновременно подстроками T и решить для них подзадачу 1. Наивное решение такого имеет асимптотическую сложность порядка O(m³ n), поскольку необходимо перебрать все подстроки P, для каждой из них перебрать позицию вхождения в T и проверить, произошло ли вхождение. При этом подзадача 1 решается за O(1).

Однако несложно заметить, что если найдено решение с общей подстрокой Q, и при этом Q можно расширить на один символ влево или вправо, то решение подзадачи 1 только уменьшится. А значит, нет необходимости перебирать все подстроки P и их вхождения. Достаточно рассмотреть те подстроки и вхождения, которые уже нельзя увеличить. Для этого фиксируем сдвиг P относительно T, и для каждого такого сдвига найдём группы повторяющихся символов. Для каждой такой группы мы и будем решать подзадачу 1. Такое решение имеет асимптотическую сложность O(nm), что приемлемо при ограничениях из условия.