Решение задачи Про суффиксные структуры с Codeforces

Бизон-Чемпион не только бизон, но и любимец команды «Бизоны».

На очередном соревновании «Бизонам» попалась следующая задача: «Даны два различных слова (строки из латинских букв) s и t. Необходимо из слова s получить слово t». Задача показалась ребятам простой, ведь они хорошо знают суффиксные структуры данных. Бизон Старший любит суффиксный автомат. Применяя его один раз к строке, он может удалить из этой строки любой один символ. Бизон Средний хорошо знает суффиксный массив. Применяя его один раз к строке, он может поменять местами два любых символа в этой строке. Суффиксным деревом ребята не владеют, а с его помощью можно сделать гораздо большее.

Бизону-Чемпиону интересно, смогут ли «Бизоны» решить задачу. При этом, возможно, для решения задачи не требуются обе структуры данных. Выясните, смогут ли ребята решить задачу и если да, то как: можно ли решить ее только с помощью суффиксного автомата, только с помощью суффиксного массива или потребуются обе структуры? Обратите внимание, что структуры разрешается использовать неограниченное количество раз и в любом порядке.