Хорошо, вот одна безумная идея.
Создать функцию, которая определяет, есть ли повторяющаяся подстрока длины k в O (n) (где n - длина текста). Это можно сделать с помощью скользящего хэша (см. Википедию Алгоритм согласования строк Рабина-Карпа ) для генерации всех n хешей за линейное время и использования хеш-таблицы / BST (или карты или dict или любого другого языка называет это), чтобы сохранить соответствующие позиции подстроки. Прежде чем вставить текущий хеш в структуру данных, мы проверяем, видели ли мы его раньше. Если это было замечено ранее, мы просто ищем индексы, где этот хеш был сгенерирован, и видим, является ли соответствующая подстрока неперекрывающимся соответствием.
Теперь, когда мы можем найти подстроку длины k за O (n), мы просто запускаем двоичный поиск, чтобы найти наибольшее k, для которого мы можем найти неперекрывающееся совпадение подстроки, используя нашу функцию.
Код в Python следует
A=23
MOD=10007 # use a random value in the real world
def hsh(text):
return sum([ord(c)*A**(len(text)-i-1) for i,c in enumerate(text)])%MOD
def k_substring(text, k):
substrings={}
cur=hsh(text[:k])
pwr=(A**(k-1))%MOD
substrings[cur]=[0]
for i in xrange(k,len(text)):
to_remove=(ord(text[i-k])*pwr)%MOD
to_add=ord(text[i])
cur-=to_remove
if cur<0:
cur+=MOD
cur=(cur*A)%MOD
cur=(cur+to_add)%MOD
if cur in substrings:
lst=substrings[cur]
for index in lst:
if index+k<=i-k+1 and text[index:index+k]==text[i-k+1:i+1]:
return index
lst.append(i-k+1)
else:
substrings[cur]=[i-k+1]
return -1
def longest_substring(text):
hi,lo=len(text),0
while hi>lo:
mid=(hi+lo+1)>>1
if k_substring(text,mid)==-1:
hi=mid-1
else:
lo=mid
index=k_substring(text,lo)
return text[index:index+lo]
(Извините, если это неясно. Сейчас 6:30 утра, и мне действительно нужно вернуться в постель :))