Geodesic
Indexing and querying character sets in one- and two-dimensional words
Fundamentalʹnaâ i prikladnaâ matematika, Tome 20 (2015) no. 6, pp. 3-16 
D. Belazzougui; R. Kolpakov; M. Raffinot. Indexing and querying character sets in one- and two-dimensional words. Fundamentalʹnaâ i prikladnaâ matematika, Tome 20 (2015) no. 6, pp. 3-16. http://geodesic.mathdoc.fr/item/FPM_2015_20_6_a0/
@article{FPM_2015_20_6_a0,
     author = {D. Belazzougui and R. Kolpakov and M. Raffinot},
     title = {Indexing and querying character sets in one- and two-dimensional words},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {3--16},
     year = {2015},
     volume = {20},
     number = {6},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2015_20_6_a0/}
}
TY  - JOUR
AU  - D. Belazzougui
AU  - R. Kolpakov
AU  - M. Raffinot
TI  - Indexing and querying character sets in one- and two-dimensional words
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2015
SP  - 3
EP  - 16
VL  - 20
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/FPM_2015_20_6_a0/
LA  - ru
ID  - FPM_2015_20_6_a0
ER  - 
%0 Journal Article
%A D. Belazzougui
%A R. Kolpakov
%A M. Raffinot
%T Indexing and querying character sets in one- and two-dimensional words
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2015
%P 3-16
%V 20
%N 6
%U http://geodesic.mathdoc.fr/item/FPM_2015_20_6_a0/
%G ru
%F FPM_2015_20_6_a0

Voir la notice de l'article provenant de la source Math-Net.Ru

We give a detailed review of results obtained for a relatively new problem of finding, indexing, and querying character sets, which are called fingerprints in fragments of one- and two-dimensional words, and explain basic ideas used for obtaining these results.

[1] Abouelhoda M. I., Kurtz S., Ohlenbusch E., “Replacing suffix trees with enhanced suffix arrays”, J. Discrete Algorithms, 2:1 (2004), 53–86 | DOI | MR | Zbl

[2] Amir A., Apostolico A., Landau G. M., Satta G., “Efficient text fingerprinting via Parikh mapping”, J. Discrete Algorithms, 1:5-6 (2003), 409–421 | DOI | MR | Zbl

[3] Belazzougui D., Kolpakov R., Raffinot M., “Various improvements to text fingerprinting”, J. Discrete Algorithms, 22 (2013), 1–18 | DOI | MR | Zbl

[4] Belazzougui D., Kolpakov R., Raffinot M., “Indexing and querying color sets of images”, Theor. Comput. Sci., 647 (2016), 74–84 | DOI | MR | Zbl

[5] Chan C.-Y., Yu H.-I., Hon W.-K., Wang B.-F., “Faster query algorithms for the text fingerprinting problem”, Inf. Comput., 209:7 (2011), 1057–1069 | DOI | MR | Zbl

[6] Didier G., Schmidt T., Stoye J., Tsur D., “Character sets of strings”, J. Discrete Algorithms, 5:2 (2007), 330–340 | DOI | MR | Zbl

[7] Kolpakov R., Raffinot M., “New algorithms for text fingerprinting”, Combinatorial Pattern Matching, 17th Annual Symp., CPM 2006, Proceedings (Barcelona, Spain, July 5–7, 2006), Lect. Notes Comput. Sci., 4009, Springer, Berlin, 2006, 342–353 | DOI | MR | Zbl

[8] Kolpakov R., Raffinot M., “New algorithms for text fingerprinting”, J. Discrete Algorithms, 6:2 (2008), 243–255 | DOI | MR | Zbl

[9] Kolpakov R., Raffinot M., “Faster text fingerprinting”, Proc. 15th Int. Symp. on String Processing and Information Retrieval, Lect. Notes Comput. Sci., 5280, Springer, Berlin, 2009, 15–26 | DOI | MR

[10] McCreight E. M., “A space-economical suffix tree construction algorithm”, J. Algorithms, 23:2 (1976), 262–272 | MR | Zbl

[11] Porat E., “An optimal bloom filter replacement based on matrix solving”, Theory and Applications, CSR '09. Proc. Fourth Int. Comput. Sci. Symp. in Russia on Comput. Sci., Lect. Notes Comput. Sci., 5675, Springer, Berlin, 2009, 263–273 | DOI | Zbl

[12] Raman R., Raman V., Rao Satti S., “Succinct indexable dictionaries with applications to encoding $k$-ary trees, prefix sums and multisets”, ACM Trans. Algorithms, 3:4 (2007), 43 | DOI | MR

[13] Ukkonen E., “Constructing suffix trees on-line in linear time”, Proc. IFIP 12th World Comput. Congr. on Algorithms, Software, Architecture, Information Processing'92, v. 1, North-Holland, Amsterdam, 1992, 484–492

[14] Weiner P., “Linear pattern matching algorithm”, Proc. 14th Annual Symp. on Switching and Automata Theory, SWAT'73, IEEE Comput. Soc., Washington, 1973, 1–11 | DOI | MR