An estimation of the size of non-vompact suffix trees
A suffix tree is a data structure used mainly for pattern matching. It is known that the space complexity of simple suffix trees is quadratic in the length of the string. By a slight modification of the simple suffix trees one gets the compact suffix trees, which have linear space complexity. The mo...
Elmentve itt :
| Szerző: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
2016
|
| Sorozat: | Acta cybernetica
22 No. 4 |
| Kulcsszavak: | Programozás |
| Tárgyszavak: | |
| doi: | 10.14232/actacyb.22.4.2016.6 |
| Online Access: | http://acta.bibl.u-szeged.hu/46422 |
| LEADER | 01228nab a2200229 i 4500 | ||
|---|---|---|---|
| 001 | acta46422 | ||
| 005 | 20220620134511.0 | ||
| 008 | 170316s2016 hu o 0|| eng d | ||
| 022 | |a 0324-721X | ||
| 024 | 7 | |a 10.14232/actacyb.22.4.2016.6 |2 doi | |
| 040 | |a SZTE Egyetemi Kiadványok Repozitórium |b hun | ||
| 041 | |a eng | ||
| 100 | 1 | |a Vásárhelyi Bálint | |
| 245 | 1 | 3 | |a An estimation of the size of non-vompact suffix trees |h [elektronikus dokumentum] / |c Vásárhelyi Bálint |
| 260 | |c 2016 | ||
| 300 | |a 113-122 | ||
| 490 | 0 | |a Acta cybernetica |v 22 No. 4 | |
| 520 | 3 | |a A suffix tree is a data structure used mainly for pattern matching. It is known that the space complexity of simple suffix trees is quadratic in the length of the string. By a slight modification of the simple suffix trees one gets the compact suffix trees, which have linear space complexity. The motivation of this paper is the question whether the space complexity of simple suffix trees is quadratic not only in the worst case, but also in expectation. | |
| 650 | 4 | |a Természettudományok | |
| 650 | 4 | |a Számítás- és információtudomány | |
| 695 | |a Programozás | ||
| 856 | 4 | 0 | |u http://acta.bibl.u-szeged.hu/46422/1/actacyb_22_4_2016_6.pdf |z Dokumentum-elérés |