Z-toiminto
Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 4. elokuuta 2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .Merkkijonon z-funktio on matriisi , joka on yhtä suuri kuin pisimmän yhteisen etuliitteen pituus, joka alkaa merkkijonon päätepaikasta , ja itse merkkijono . Rakennusalgoritmin kuvaili Dan Gasfield kirjassaan Strings, Trees and Sequences in Algorithms. Computer Science and Computational Biology” vuonna 1997 [1] perustui Mainen ja Lorenzin vuoden 1984 artikkeliin [2] kaikkien tandemtoistojen löytämisestä merkkijonosta.
Z -funktiota käytetään useissa merkkijonojen käsittelyalgoritmeissa. Erityisesti sitä voidaan käyttää ratkaisemaan nopeasti ongelma, joka liittyy merkkijonon esiintymisen löytämiseen toisessa ( haku kuvion mukaan ).
Laskenta-algoritmi
Rivimerkit numeroidaan 0:sta alkaen.Tallennamme indeksit L ja R , jotka osoittavat suurimman tähän mennessä löydetyn R -arvon etuliitteen alkua ja loppua . Aluksi .
Selvitetään Z -funktion arvot paikoille 1… i − 1. Yritetään laskea Z -funktion arvo paikalle i . Jos , harkitse paikan Z - funktion arvoa . Jos , niin , koska olemme osamerkkijonossa, joka vastaa koko merkkijonon etuliitettä. Jos , niin Z [ i ]: n arvo on laskettava yksinkertaisella silmukalla, joka kulkee R :n jälkeisten merkkien läpi, kunnes löytyy merkki, joka ei vastaa vastaavaa etuliitteen merkkiä. Tämän jälkeen muutamme L :n arvon i :ksi ja R :n arvon viimeisen merkin numeroon, joka vastaa etuliitteen vastaavaa merkkiä.
![i \in [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)
Jos , niin katsomme Z :n [ i ] arvoa yksinkertaisena silmukana, joka vertaa i :nnellä merkillä alkavan osamerkkijonon merkkejä ja vastaavia etuliitteen merkkejä. Kun ristiriita löytyy tai rivin loppu on saavutettu, muuta L : n arvo i :ksi ja R :n arvoksi sen viimeisen merkin numero, joka vastaa etuliitteen vastaavaa merkkiä.
![en ole [L..R]](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7bc389ea5d3117fde5679222adc74f9a2262385)
Työn nopeus
Merkkijonon S Z -funktion arvon laskevan algoritmin ajoaika on estimoitu . Todistetaan se.
Harkitse merkkijonon i -merkkiä. Algoritmissa sitä tarkastellaan enintään kahdesti: ensimmäisen kerran, kun se osuu segmenttiin ja toisen kerran laskettaessa Z [ i ].
Siten silmukka käsittelee vain iteraatioita.
Käyttöesimerkkejä
1) Z -funktiolla voidaan etsiä kuviota T merkkijonosta S ,
2) Tietäen merkkijonon Z -funktion, voidaan yksilöllisesti palauttaa tämän merkkijonon etuliitefunktio ja päinvastoin.
Toteutusesimerkki Pythonissa
def z_func ( s ): z = [ 0 ] * len ( t ) vasen , oikea = 0 , 0 i :lle alueella ( 1 , len ( t ) ): z [ i ] = max ( 0 , min ( z [ i - vasen ], oikea - i )) kun taas i + z [ i ] < len ( t ) ja s [ z [ i ]] == s [ i + z [ i ]]: z [ i ] += 1 jos i + z [ i ] > oikea : vasen , oikea = i , i + z [ i ] palauta zKatso myös
Muistiinpanot
- ↑ Gusfield D. Algorithms on Strings, Trees ja Sequences (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. O(n log n) -algoritmi merkkijonon kaikkien toistojen löytämiseksi // Journal of Algorithms - Academic Press , 1984. - Voi. 5, Iss. 3. - s. 422-432. — ISSN 0196-6774 ; 1090-2678 - doi:10.1016/0196-6774(84)90021-X
Linkit
- Artikkeli aiheesta MAXimal::algo
- Tarkistettava tehtävä (linkki ei saatavilla)
| jouset | |
|---|---|
| Merkkijonojen samankaltaisuusmitat | |
| Alimerkkijonohaku | |
| palindromit | |
| Jakson tasaus | |
| Suffiksirakenteet | |
| Muut | |