Z-funktion
Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 4. august 2021; verifikation kræver 1 redigering .Z-funktionen af en streng er en matrix , så den er lig med længden af det længste fælles præfiks , der starter ved strengens suffiksposition og strengen selv . Konstruktionsalgoritmen blev beskrevet af Dan Gasfield i hans bog Strings, Trees and Sequences in Algorithms. Computer Science and Computational Biology” i 1997 [1] baseret på Maine og Lorenz' papir fra 1984 [2] om at finde alle tandemgentagelser i en streng.
Z -funktionen bruges i forskellige strengbehandlingsalgoritmer. Det kan især bruges til hurtigt at løse problemet med at finde en forekomst af en streng i en anden ( søg efter mønster ).
Beregningsalgoritme
Linjetegn er nummereret fra 0.Vi gemmer indeks L og R , der angiver begyndelsen og slutningen af præfikset med den hidtil største R- værdi . Indledningsvis .
Lad os kende værdierne af Z - funktionen for positioner 1… i − 1. Lad os prøve at beregne værdien af Z - funktionen for position i . Hvis , overvej værdien af Z -funktionen for positionen . Hvis , så , da vi er i en understreng, der matcher præfikset for hele strengen. Hvis , så er det nødvendigt at beregne værdien af Z [ i ] ved en simpel løkke, der går gennem tegnene efter R , indtil der er et tegn, der ikke matcher det tilsvarende tegn fra præfikset. Derefter ændrer vi værdien af L til i og værdien af R til tallet på det sidste tegn, der matcher det tilsvarende tegn fra præfikset.
![i \i [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)
Hvis , så betragter vi værdien af Z [ i ] som en simpel løkke, der sammenligner tegnene i understrengen begyndende med det i -te tegn og de tilsvarende tegn fra præfikset. Når der er fundet en uoverensstemmelse eller slutningen af linjen nås, skal du ændre værdien af L til i og værdien af R til tallet på det sidste tegn, der matcher det tilsvarende tegn fra præfikset.
![i \notin [L..R]](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7bc389ea5d3117fde5679222adc74f9a2262385)
Arbejdshastighed
Køretiden for den algoritme, der beregner værdien af Z -funktionen af strengen S , estimeres til . Lad os bevise det.
Overvej strengens i -te karakter. I algoritmen betragtes det ikke mere end to gange: første gang, når det falder ind i segmentet, og anden gang, når man beregner Z [ i ].
Løkken behandler således ikke mere end iterationer.
Eksempler på brug
1) Z - funktionen kan bruges til at søge efter et mønster T i en streng S ,
2) Ved at kende Z - funktionen af en streng, kan man entydigt gendanne denne strengs præfiks-funktion , og omvendt.
Implementeringseksempel i Python
def z_func ( s ): z = [ 0 ] * len ( s ) venstre , højre = 0 , 0 for i inden for rækkevidde ( 1 , len ( s )): z [ i ] = maks ( 0 , min ( z [ i - venstre ], højre - i )) mens i + z [ i ] < len ( s ) og s [ z [ i ]] == s [ i + z [ i ]]: z [ i ] += 1 hvis i + z [ i ] > højre : venstre , højre = i , i + z [ i ] returnere zSe også
Noter
- ↑ Gusfield D. Algoritmer om strenge, træer og sekvenser (Eng.) : Computer Science and Computational Biology - Cambridge University Press , 1997. - 556 s. - ISBN 978-0-511-57493-1 - doi:10.1017/CBO9780511574931
- ↑ Main M. G., Lorentz R. J. En O(n log n) algoritme til at finde alle gentagelser i en streng // Journal of Algorithms - Academic Press , 1984. - Vol. 5, Iss. 3. - S. 422-432. — ISSN 0196-6774 ; 1090-2678 - doi:10.1016/0196-6774(84)90021-X
Links
- Artikel om MAXimal::algo
- Opgave at tjekke (utilgængeligt link)
| Strenge | |
|---|---|
| String lighedsmål | |
| Understrengssøgning | |
| palindromer | |
| Sekvensjustering | |
| Suffiksstrukturer | |
| Andet | |