Funcția Z
Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 4 august 2021; verificarea necesită 1 editare .Funcția z a unui șir este o matrice astfel încât este egală cu lungimea celui mai lung prefix comun, începând de la poziția sufixului șirului și a șirului în sine . Algoritmul de construcție a fost descris de Dan Gasfield în cartea sa Strings, Trees and Sequences in Algorithms. Computer Science and Computational Biology” în 1997 [1] pe baza lucrării lui Maine și Lorenz din 1984 [2] privind găsirea tuturor repetăților în tandem într-un șir.
Funcția Z este utilizată în diverși algoritmi de procesare a șirurilor. În special, poate fi folosit pentru a rezolva rapid problema găsirii unei apariții a unui șir în altul ( căutare după model ).
Algoritm de calcul
Caracterele rând sunt numerotate de la 0.Vom stoca indicii L și R , notând începutul și sfârșitul prefixului cu cea mai mare valoare R găsită până acum . Initial .
Aflați-ne valorile funcției Z pentru pozițiile 1… i − 1. Să încercăm să calculăm valoarea funcției Z pentru poziția i . Dacă , luați în considerare valoarea funcției Z pentru poziția . Dacă , atunci , deoarece ne aflăm într-un subșir care se potrivește cu prefixul întregului șir. Dacă , atunci este necesar să se calculeze valoarea lui Z [ i ] printr-o buclă simplă care trece prin caracterele după R până când apare un caracter care nu se potrivește cu caracterul corespunzător din prefix. După aceea, schimbăm valoarea lui L în i și valoarea lui R cu numărul ultimului caracter care se potrivește cu caracterul corespunzător din prefix.
![i \în [L..R]](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fe0f4210173b6b36cf50743eb42ef04136f6b2d)
![i + Z[j] \leqslant R](https://wikimedia.org/api/rest_v1/media/math/render/svg/83b84625c3595c8646681ed1dc8221bb962b12da)
![Z[i] = Z[j]](https://wikimedia.org/api/rest_v1/media/math/render/svg/f870c16cc4149c1355767b45cd2e71b80484f211)
![i + Z[j] > R](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cf0ccebb8ddeca7d44d7b978fad0b6ed3eac6be)
Dacă , atunci considerăm valoarea lui Z [ i ] ca o simplă buclă care compară caracterele subșirului începând cu caracterul i -lea și caracterele corespunzătoare din prefix. Când se găsește o nepotrivire sau se ajunge la sfârșitul liniei, schimbați valoarea lui L la i și valoarea lui R la numărul ultimului caracter care se potrivește cu caracterul corespunzător din prefix.
![eu \notin [L..R]](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7bc389ea5d3117fde5679222adc74f9a2262385)
Viteza de lucru
Timpul de rulare al algoritmului care calculează valoarea funcției Z a șirului S este estimat la . Să demonstrăm.
Luați în considerare caracterul i --lea al șirului. În algoritm, este considerat nu mai mult de două ori: prima dată când cade în segment și a doua oară când se calculează Z [ i ].
Astfel, bucla nu procesează mai mult decât iterații.
Exemple de utilizare
1) Funcția Z poate fi folosită pentru a căuta un model T într-un șir S ,
2) Cunoscând funcția Z a unui șir, se poate restabili în mod unic funcția-prefix a acestui șir și invers.
Exemplu de implementare în Python
def z_func ( s ): z = [ 0 ] * len ( s ) stânga , dreapta = 0 , 0 pentru i în interval ( 1 , len ( s )): z [ i ] = max ( 0 , min ( z [ i - stânga ], dreapta - i )) în timp ce i + z [ i ] < len ( s ) și s [ z [ i ]] == s [ i + z [ i ]]: z [ i ] += 1 dacă i + z [ i ] > dreapta : stânga , dreapta = i , i + z [ i ] întoarce zVezi și
Note
- ↑ Gusfield D. Algorithms on Strings, Trees, and Sequences (Eng.) : Computer Science and Computational Biology - Cambridge University Press , 1997. - 556 p. - ISBN 978-0-511-57493-1 - doi:10.1017/CBO9780511574931
- ↑ Main M. G., Lorentz R. J. Un algoritm O(n log n) pentru găsirea tuturor repetițiilor într-un șir // Journal of Algorithms - Academic Press , 1984. - Vol. 5, Iss. 3. - P. 422-432. — ISSN 0196-6774 ; 1090-2678 - doi:10.1016/0196-6774(84)90021-X
Link -uri
- Articol pe MAXimal::algo
- Sarcină de verificat (link indisponibil)
| Siruri de caractere | |
|---|---|
| Măsuri de similitudine a șirurilor | |
| Căutare subșir | |
| palindromuri | |
| Alinierea secvenței | |
| Structuri de sufix | |
| Alte | |