Funcția de prefix

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 12 aprilie 2022; verificările necesită 4 modificări .

Funcția de prefix a unui șir și o poziție în acesta este lungimea celui mai mare prefix propriu (nu este egal cu întregul subșir) al subșirului , care este și sufixul acestui subșir. $S$ $i$ $k$ $S[1..i]$

Adică, la începutul unui subșir de lungime , trebuie să găsiți un astfel de prefix de lungime maximă care ar fi sufixul acestui subșir . $S[1..i]$ $i$ $k<i$ $\left(S[1..k]=S\left[(i-k+1)..i\right]\right)$

Notat ; unde este un șir; este lungimea subşirului în S. Se presupune că . $\pi (S,i)$ $S\in \Sigma ^{+)$ $1\leqslant i\leqslant \left|S\right|$ $\pi (S,1)=0$

Adesea funcția de prefix este definită sub formă vectorială:

Funcția de prefix a unui șir este un vector , fiecare element fiind egal cu . $S\in \Sigma ^{+)$ $\pi (S)\in \mathbb {Z} ^{\left|S\right|)$ $i$ $\pi (S,i)$

De exemplu, pentru un șir, funcția de prefix ar fi: . ${\texttt {abcdabscabcdabia}}$ $\pi ({\texttt {abcdabscabcdabia}))=[0,0,0,0,1,2,0,0,1,2,3,4,5,6,0,1]$

Această funcție este utilizată, de exemplu, în algoritmul Knuth-Morris-Pratt .

Algoritm de calcul

Caută silabe repetate nu într-un cuvânt, ci într-un text, o linie care începe de la primele caractere? Caracterele rând sunt numerotate de la 1.

Lasă . Să încercăm să calculăm funcția de prefix pentru . $\pi (S,i)=k$ $i+1$

Dacă , atunci, desigur, . Dacă nu, încercați sufixe mai mici. Nu este necesar să repetați toate sufixele cu o căutare liniară. Puteți utiliza valorile deja calculate ale funcției de prefix. Puteți vedea că acesta va fi și sufixul șirului , deoarece este lungimea prefixului-sufix maxim în acest moment. Pentru orice șir, nu va exista sufix. Astfel, algoritmul rezultă: $S[i+1]=S[k+1]$ $\pi (S,i+1)=k+1$ $S[1\ldots \pi (S,k)]$ $S[1\ldots i]$ $k$ $j\in(k,i)$ $S[1\ldots j]$

Când - pune . $S[i+1]=S[k+1]$ $\pi (S,i+1)=k+1$
În caz contrar, când - pune . $k=0$ $\pi (S,i+1)=0$
În caz contrar, instalați și treceți la pasul 1. $k:=\pi (S,k)$

Pentru un șir , 'abcdabcabcdabcdab'calculul ar fi:

1 S[1]='a', k=π=0; 2 S[2]='b'!=S[k+1] => k=π=0; 3 S[3]='c'!=S[1] => k=π=0; 4 S[4]='d'!=S[1] => k=π=0; 5 S[5]='a'==S[1] => k=π=1; 6 S[6]='b'==S[2] => k=π=2; 7 S[7]='c'==S[3] => k=π=3; 8 S[8]='a'!=S[4] => k:=π(S, 3)=0, S[8]==S[1] => k=π=1; 9 S[9]='b'==S[2] => k=π=2; 10 S[10]='c'==S[3] => k=π=3; 11 S[11]='d'==S[4] => k=π=4; 12 S[12]='a'==S[5] => k=π=5; 13 S[13]='b'==S[6] => k=π=6; 14 S[14]='c'==S[7] => k=π=7; 15 S[15]='d'!=S[8] => k:=π(S, 7)=3, S[15]==S[4] => k=π=4; 16 S[16]='a'==S[5] => k=π=5; 17 S[17]='b'==S[6] => k=π=6;

Iar rezultatul este: [0,0,0,0,1,2,3,1,2,3,4,5,6,7,4,5,6].

Viteza de lucru

În ciuda faptului că elementul 3 este o buclă interioară, timpul de calcul al funcției de prefix este estimat ca . Să demonstrăm. $O(|S|)$

Toate sunt împărțite în: $i$

crescând cu unu. Bucla trece printr-o iterație. $k$
Nu se schimbă zero . De asemenea, bucla trece printr-o iterație. Cazurile 1 și 2 în total nu mai mult de bucăți. $k$ $\left|S\right|-1$
Nu schimbați sau reduceți pozitivul . Deoarece valoarea poate scădea doar în interiorul buclei, iar creșterea este posibilă doar cu una, valoarea totală nu poate scădea de mai multe ori, ceea ce limitează numărul de ori se execută bucla interioară. $k$ $k$ $k$ $k$ $\left|S\right|-2$

În total, algoritmul nu necesită mai mult decât iterații, ceea ce demonstrează ordinea vitezei . „Cel mai rău” pentru algoritm este cazul procesării unui șir de forma . $2\left|S\right|$ $O(\left|S\right|)$ 'aa…ab'

Exemplu de implementare în Python

def prefix ( s ): p = [ 0 ] * len ( s ) pentru i în interval ( 1 , len ( s )): k = p [ i - 1 ] în timp ce k > 0 și s [ k ] != s [ i ]: k = p [ k - 1 ] dacă s [ k ] == s [ i ]: k += 1 p [ i ] = k return p

Link -uri

Căutare sub șir și întrebări conexe Arhivate 15 ianuarie 2016 la Wayback Machine - Articolul Habr

Siruri de caractere
Măsuri de similitudine a șirurilor	Distanța de la Damerau la Loewenstein Distanța Levenshtein Distanța de Hamming Asemănări Jaro-Winkler
Căutare subșir	Algoritmul Boyer-Moore Algoritmul Boyer-Moore-Horspool Algoritmul Knuth-Morris-Pratt Algoritmul Rabin-Karp funcția de prefix Funcția Z Algoritmul Aho - Korasik
palindromuri	arbore palindrom Algoritmul lui Manaker
Alinierea secvenței	Algoritmul Needleman-Wunsha Algoritmul Smith-Waterman
Structuri de sufix	Matrice de sufixe Sufix automat arbore de sufix arbore de prefix
Alte	analizare Potrivire de model Cea mai mare succesiune comună Cel mai mare subșir comun