È possibile contare il numero di sottostringhe distinte in una stringa in O (n)?

Question

Dato una stringa s di lunghezza n, è possibile contare il numero di sottostringhe distinte in s in O (n)?

Esempio

ingresso: abb

uscita: 5 ('abb', 'ab', 'bb', 'a', 'b')

Ho fatto qualche ricerca, ma io non riesco a trovare un algoritmo che risolve questo problema in un tale maniera efficiente. So che un approccio O (n^2) è possibile, ma esiste un algoritmo più efficiente?

Non è necessario ottenere ciascuna delle sottostringhe, ma solo il numero totale di distinte (nel caso in cui faccia la differenza).

Answer 1

È possibile utilizzare l'algoritmo di Ukkonen per costruire un albero suffisso nel tempo lineare:

https://en.wikipedia.org/wiki/Ukkonen%27s_algorithm

Il numero di stringhe di s è allora il numero di prefissi di stringhe nel trie, che è possibile calcolare semplicemente in tempo lineare. È solo il numero totale di personaggi in tutti i nodi.

Per esempio, il vostro esempio produce un albero suffisso come:

  /\     
      b a 
      | b 
      b b 

5 caratteri nella struttura, in modo da 5 stringhe. Ogni stringa univoca è un percorso dalla radice che termina dopo una lettera diversa: abb, ab, a, bb, b. Quindi il numero di stringhe è il numero di lettere nell'albero.

Più precisamente:

• Ogni stringa è il prefisso di alcuni suffisso della stringa;
• Tutti i suffissi sono nel trie;
• Quindi c'è una corrispondenza di 1-1 tra sottostringhe e percorsi attraverso il trie (dalla definizione di trie); e
• esiste una corrispondenza tra 1-1 lettere nei viali e non vuoti, perché:
  • ogni percorso non vuoto distinta termina in una posizione distinta dopo l'ultima lettera; e
  • il percorso per la posizione dopo ogni lettera è unico

NOTA per le persone che si stanno chiedendo come potrebbe essere possibile costruire un albero che contiene (N^2) caratteri O a O (N) tempo:

C'è un trucco per la rappresentazione di un albero di suffisso. Invece di memorizzare le stringhe reali nei nodi dell'albero, basta semplicemente memorizzare i puntatori nella stringa originale, quindi il nodo che contiene "abb" non ha "abb", ha (0,3) - 2 interi per nodo, indipendentemente dalla lunghezza della stringa in ciascun nodo e l'albero del suffisso ha nodi O (N).

Answer 2

Costruire il LCP array e sottrarre la sua somma dal numero di sottostringhe (n (n + 1)/2).