Собственно, вопрос такой: можно ли решать эту задачу пропусканием второй строки по дереву первой? Убил весь вечер, переписал кучу квадратоподобных вариантов, но они даже не были верными.

P.S.: Как делать это, строя дерево для сконкатенированной строки, знаю.