Моя проблема похожа на поиск самых длинных повторяющихся непересекающихся подстрок, но таким образом. Пример, мой входной массив 0,0,0,1,2,1,1,2,1,1,2,1,2,0,0
Самая длинная повторяющаяся и непересекающаяся подстрока в этом входе — 121 со счетчиком 3. Теперь удалите вхождения 121 из входного массива и замените их на -1.
Мой ввод теперь выглядит так: 0,0,0,-1,-1,-1,2,0,0 Теперь снова найдите те же подстроки.
Примечание: -1 не должен быть включен в ответ. Таким образом, следующая самая длинная непересекающаяся и повторяющаяся подстрока — это 00 со счетчиком 2.
Удалите вхождения 0,0 из входных данных, которые тогда станут: 0,-1,-1,-1,2,-1 Теперь единственными вхождениями являются 0 и 2, которые имеют длину 1. Итак, здесь мы останавливаемся.
Я могу думать только о грубой силе, которая будет O (n3). Пытался думать и о деревьях суффиксов, но не знаю, как включить в него неперекрывающееся условие.
Моя очень наивная реализация:
Поскольку я хочу, чтобы моя подстрока имела счет как минимум 2, она может иметь максимальную длину как N/2 (N - размер входного массива)
for len = N/2 to 1:
// find all sub-strings of length as "len" in the input sequence
for i=0 to N-len+1
// the sub-string is s[i... (i+len)]
// find non-overlapping count of this sub-string in the input sequence using KMP
int count = find_Count();
// take the substring with maximum count, let it be "r"
end
modify the array to place replace non-overlapping occurrences of "r" with -1
end
Как видно выше, сложность составляет O(N3).
Любое оптимальное решение, подсказка или объяснение могут помочь.
Спасибо
