Учитывая строку S, я хочу найти повторяющуюся подстроку S (мы будем называть подстроку 'X') такой, что:
- 1
- 1 <вхождения X </li>
- Значение
(X.length) * (occurrences of X) максимально увеличено.
Это будет приблизительно найти подстроку, которая обеспечит наибольшее сжатие при замене всехвхождения подстроки с одним символом токена.
Это выполнимо за полиномиальное время?
Если нет, существуют ли эвристики или подходы, позволяющие сократить практическое время работы этого алгоритма?