Салют! Есть такая интересная задача. Начиная с пустой строки путём добавления одного

любого символа либо копирования любой части уже получившейся строки, построить целевую строку. Операции добавления и копирования имеют определённую стоимость. Необходимо найти наименьшую стоимость получения целевой строки.

Пример 1. Целевая строка — "abab". Цена добавления — 2, копирования — 3.
- Начинаем с пустой строки "".
- Добавляем символ "a" (цена 2): "a"
- Добавляем символ "b" (цена 2): "ab"
- Копируем "ab" (цена 3): "abab"
Итого минимальная цена строки = 7.

Пример 2. Целевая строка — "ayawyayawr". Цена добавления — 6, копирования — 8.
- Начинаем с пустой строки "".
- Добавляем "a" (цена 6): "a"
- Добавляем "y" (цена 6): "ay"
- Добавляем "a" (цена 6): "aya"
- Добавляем "w" (цена 6): "ayaw"
- Добавляем "y" (цена 6): "ayawy"
- Копируем "ayaw" (цена 8): "ayawyayaw"
- Добавляем "r" (цена 6) : "ayawyayawr"
Итого минимальная цена строки = 44.

Есть идея реализации за квадрат.

Но нужно быстрее (линия или n*log n).
Есть мыли на этот счёт?

А как вы решили за квадрат? Возможно, есть смысл найти там узкое место и подобрать структуру данных под его ускорение

Через z-функцию всех подстрок.

но граф то ациклический

Там мультиребро за более раннее вхождение

Липатов говорил, что автор сего афоризма про логарифм -- Ландау, но возможно, что "музыка и слова народные"

Могу предоставить что это он, впрочем как и то что ему это приписали)

очевидно нет

К тебе специальный вопрос https://t.me/proalgorithms/98421

а ты хочешь это чтобы с кешом лучше дружило?

очевидно