Восстановить строку из n непрерывных подстрок фиксированной длины
В качестве входных данных у меня есть список из n+2 непрерывных подстрок длины 3. Моя цель — выяснить, существует ли строка длины n такая, что все ее непрерывные подстроки длины 2 точно совпадают со входным списком, который мне дали.
Как я могу эффективно решить эту проблему (например, для строк длиной 4000)?
Я попробовал подход DP, аналогичный тому, который используется для умножения цепочек матриц, но он не сработал.
Теперь я думаю, что мог бы преобразовать эту задачу в граф, где подстроки являются вершинами, а две вершины (подстроки длины 3) соединены ребром, если подстроки можно соединить в подстроку длины 4 (например, abc и bcd связаны, так как их можно соединить в abcd). Попытка найти эйлеров путь в этом графе решит мою проблему? Или я совершенно не прав во всем этом?