Funzione prefisso, funzione Z


Per risolvere questo problema, la solita enumerazione non funzionerà, perché i suoi asintotici saranno O(t*s). Pertanto, per le attività di ricerca di sottostringhe, viene utilizzato l'algoritmo KMP (Knuth-Morris-Pratt).
Per implementare questo algoritmo, viene utilizzata la funzione prefisso stringa, che è un array di numeri di lunghezza n (strong>s length), in cui ogni elemento è la  lunghezza massima del suffisso più grande della sottostringa s, corrispondente al suo prefisso. Ad esempio:
 
Linea Funzione prefisso Nota
abababcab 0 0 1 2 3 4 0 1 2  
abcabcd 0 0 0 1 2 3 0  
aabaaab 0 1 0 1 2 2 3  

Algoritmo banale per la funzione del prefisso con asintotici O(n^3):

vettore<int> funzione_prefisso (stringa s) {
int n = (int ) s.lunghezza();
vettore<int>pi(n);
per (int i=0; i<n; ++i)
per (int k=0; k<=i; ++k)
if (s.substr(0,k) == s .substr(i-k+1,k))
pi[i] = k;
ritornopi greco;
}

E ora dobbiamo creare una funzione prefisso per una stringa della forma: & nbsp; t + # + s, dove # è un carattere delimitatore chiaramente non presente nel testo.  Analizzando i valori della funzione prefisso dopo il carattere separatore corrispondente, va notato che se il valore risultante è uguale alla lunghezza della sottostringa desiderata, viene trovata la sua occorrenza. Ad esempio, per la stringa "abababcab" e la sottostringa desiderata "abab", la funzione prefisso sarà:
0 0 1 2 0 1 2 3 4 3 4 0 1 2 dobbiamo analizzare gli elementi della stringa corrispondente s:
1 2 3 4 3 4 0 1 2 - ci sono due casi in cui il valore è 4 (4° e 6°), cioè lunghezza t,  di conseguenza, la risposta deve essere scritta: 4 - 4 (lunghezza t) & nbsp; = 0 e 6 - 4 = 2. Si può vedere che queste sono le risposte corrette e la stringa "abab" è in realtà una sottostringa nella stringa "abababcab" nelle posizioni 0 e 2.

 

Training problem

(C++) Ricerca di sottostringhe, KMP, variante banale: Start

Dopo aver ottimizzato la funzione del prefisso (per i dettagli qui ), otteniamo l'algoritmo finale con O(n) asintotici:

vettore<int> funzione_prefisso (stringa s) {
int n = (int ) s.lunghezza();
vettore<int>pi(n);
per (int i=1; i<n; ++i) {
int j = pi[i-1< /span>];
mentre (j > 0 && s[i] != s[j])
j = pi[j-1];
if (s[i] == s[j]) ++j;
pi[i] = j;
}
ritornopi greco;
}

Training problem

funzione di prefisso

Z-funzione
Z-funzione dalla stringa S - array Z, ogni elemento del quale è Z [i ] è uguale al prefisso più lungo della sottostringa che inizia alla posizione i nella stringa S, che è anche il prefisso dell'intera stringa Z. Il valore della funzione Z alla posizione zero è solitamente zero o la lunghezza dell'intera stringa.
Difficoltà
O(|S| ^ 2) o O(|S|).
 
Funzione di prefisso dalla stringa S - array P, ogni elemento di cui P[i] è uguale al suffisso più lungo del sottostringa a partire dalla posizione i nella stringa S, che è anche il suffisso dell'intera stringa S. Il valore della P-funzione alla posizione zero è solitamente zero o la lunghezza dell'intera stringa. 
Difficoltà
O(|S| ^ 2) o O(|S|).
 
Prova ad implementare la funzione Z e la funzione prefisso per O(|S| ^ 2) .

Training problem

Funzione Z

 
Sia Z che il prefisso della funzione possono essere usati per implementare l'algoritmo KMP(Knuth-Morris-Pratt) per trovare una sottostringa in una stringa in O(|S|). L'essenza di questo algoritmo è la seguente: attribuiamo alla stringa che vogliamo trovare la stringa in cui stiamo cercando. È altamente desiderabile inserire un carattere separatore tra queste righe, ovvero un carattere che non ricorre in nessuna riga (di solito #).

Training problem

Cifra