Z-funkce
Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 4. srpna 2021; ověření vyžaduje 1 úpravu .Funkce z řetězce je pole takové, že se rovná délce nejdelší společné předpony začínající na pozici přípony řetězce a samotného řetězce . Konstrukční algoritmus popsal Dan Gasfield ve své knize Strings, Trees and Sequences in Algorithms. Computer Science and Computational Biology“ v roce 1997 [1] na základě práce Mainea a Lorenze z roku 1984 [2] o nalezení všech tandemových opakování v řetězci.
Funkce Z se používá v různých algoritmech zpracování řetězců. Zejména jej lze použít k rychlému vyřešení problému s nalezením výskytu jednoho řetězce v jiném ( vyhledávání podle vzoru ).
Algoritmus výpočtu
Znaky řádků jsou číslovány od 0.Budeme ukládat indexy L a R , označující začátek a konec prefixu s největší dosud zjištěnou hodnotou R . Zpočátku .
Dejte nám vědět hodnoty Z -funkce pro pozice 1… i − 1. Zkusme vypočítat hodnotu Z -funkce pro pozici i . Pokud , zvažte hodnotu funkce Z pro pozici . If , then , protože jsme v podřetězci, který odpovídá prefixu celého řetězce. Jestliže , pak je nutné vypočítat hodnotu Z [ i ] jednoduchou smyčkou, která prochází znaky za R , dokud se neobjeví znak, který neodpovídá odpovídajícímu znaku z předpony. Poté změníme hodnotu L na i a hodnotu R na číslo posledního znaku, který odpovídá odpovídajícímu znaku z prefixu.
![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)
Jestliže , pak považujeme hodnotu Z [ i ] za jednoduchou smyčku, která porovnává znaky podřetězce začínající i -tým znakem a odpovídající znaky z prefixu. Když je nalezena neshoda nebo je dosaženo konce řádku, změňte hodnotu L na i a hodnotu R na číslo posledního znaku, který odpovídá odpovídajícímu znaku z předpony.
![i \notin [L..R]](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7bc389ea5d3117fde5679222adc74f9a2262385)
Rychlost práce
Doba běhu algoritmu, který vypočítává hodnotu Z -funkce řetězce S , se odhaduje na . Pojďme to dokázat.
Uvažujme i -tý znak řetězce. V algoritmu se bere v úvahu maximálně dvakrát: poprvé, když spadá do segmentu , a podruhé při výpočtu Z [ i ].
Smyčka tedy nezpracovává více než iterace.
Příklady použití
1) Funkci Z lze použít k vyhledání vzoru T v řetězci S ,
2) Se znalostí Z - funkce řetězce lze jednoznačně obnovit prefixovou funkci tohoto řetězce a naopak.
Příklad implementace v Pythonu
def z_func ( s ): z = [ 0 ] * délka ( s ) vlevo , vpravo = 0 , 0 pro i v rozsahu ( 1 , len ( s )): z [ i ] = max ( 0 , min ( z [ i - vlevo ], vpravo - i )) zatímco i + z [ i ] < len ( s ) a s [ z [ i ]] == s [ i + z [ i ]]: z [ i ] += 1 pokud i + z [ i ] > vpravo : vlevo , vpravo = i , i + z [ i ] vrátit zViz také
Poznámky
- ↑ Gusfield D. Algorithms on Strings, Trees, and Sequences (Angl.) : 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. Algoritmus O(n log n) pro nalezení všech opakování v řetězci // 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
Odkazy
- Článek na MAXimal::algo
- Úkol ke kontrole (nedostupný odkaz)
| Struny | |
|---|---|
| Míry podobnosti řetězců | |
| Hledání podřetězců | |
| palindromy | |
| Sekvenční zarovnání | |
| Struktury přípon | |
| jiný | |