più lunga sottostringa che appare n volte

Question

Per una stringa di lunghezza L, voglio trovare la stringa più lunga che appare n (n < L) o più volte in THS stringa.

Ad esempio, la sottostringa più lunga che si verifica 2 o più volte in "BANANA" è "ANA", una volta a partire dall'indice 1 e nuovamente a partire dall'indice 3. Le sottostringhe possono sovrapporsi.

Nella stringa "FFFFFF", la stringa più lunga che appare 3 o più volte è "FFFF".

L'algoritmo a forza bruta per n = 2 sarebbero selezionando tutte le coppie di indici nella stringa, quindi eseguendo lungo finché i caratteri sono diversi. La parte da corsa prende O (L) e il numero di coppie è O (L^2) (i duplicati non sono consentiti ma lo ignoro) quindi la complessità di questo algoritmo per n = 2 sarebbe O (L^3). Per maggiori valori di n, questo cresce in modo esponenziale.

Esiste un algoritmo più efficiente per questo problema?

Answer 1

Gli alberi di suffisso risolvono questo tipo di problemi molto velocemente, di solito O (n), tempo e spazio.

Guardate la pagina wiki:

Suffix Trees.

e leggere il materiale (la sezione funzionalità) in quella pagina che collega a:

Longest Repeated Substring.

Answer 2

Longest common substring problem