Ok, ecco una pazza idea.
Creare una funzione che determina se esiste una sottostringa ricorrente di lunghezza k in O (n) (dove n è la lunghezza del testo). Questo può essere fatto usando un hash rolling (vedi wikipedia per Rabin-Karp String Matching Algorithm) per generare tutti gli n hash in tempo lineare e usando un hashtable/BST (o una mappa o dict o qualsiasi altra lingua la chiami) per memorizzare le posizioni di sottostringa corrispondenti. Prima di inserire l'attuale hash nella struttura dati, controlliamo se l'abbiamo già visto prima.Se è stato visto prima, cerchiamo semplicemente gli indici in cui è stato generato questo hash e vediamo se la sottostringa corrispondente è una corrispondenza non sovrapposta.
Ora che possiamo trovare una sottostringa di lunghezza k nel tempo O (n), eseguiamo semplicemente una ricerca binaria per trovare il k più grande per il quale possiamo trovare una corrispondenza di sottostringa non sovrapposta usando la nostra funzione.
codice in Python segue
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]
(Scusate se questo non è chiaro. E '6:30 qui e ho davvero bisogno di tornare a letto :))
proprio curious- qual è l'applicazione aziendale per questo? – Beth
Non è un'applicazione aziendale. È legato al trovare il tema in una canzone ed è più una curiosità al momento finché non avrò un progetto che coinvolge questo. =] –