On Table Arrangements, Scrabble Freaks, and Jumbled Pattern Matching

Burcsi P, Cicalese F, Fici G, Lipták Z (2010)
In: Fun with Algorithms: 5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010. Proceedings. Boldi P (Ed); Lecture Notes in Computer Science, 6099. Berlin, Heidelberg: Springer: 89-101.

Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Konferenzbeitrag | Veröffentlicht | Englisch
Autor
; ; ;
Herausgeber
Abstract / Bemerkung
Given a string s, the Parikh vector of s, denoted p(s), counts the multiplicity of each character in s. Searching for a match of Parikh vector q (a “jumbled string”) in the text s requires to find a substring t of s with p(t) = q. The corresponding decision problem is to verify whether at least one such match exists. So, for example for the alphabet Σ = {a, b, c}, the string s = abaccbabaaa has Parikh vector p(s) = (6,3,2), and the Parikh vector q = (2,1,1) appears once in s in position (1,4). Like its more precise counterpart, the renown Exact String Matching, Jumbled Pattern Matching has ubiquitous applications, e.g., string matching with a dyslectic word processor, table rearrangements, anagram checking, Scrabble playing and, allegedly, also analysis of mass spectrometry data. We consider two simple algorithms for Jumbled Pattern Matching and use very complicated data structures and analytic tools to show that they are not worse than the most obvious algorithm. We also show that we can achieve non-trivial efficient average case behavior, but that’s less fun to describe in this abstract so we defer the details to the main part of the article, to be read at the reader’s risk...well, at the reader’s discretion.
Erscheinungsjahr
Titel des Konferenzbandes
Fun with Algorithms: 5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010. Proceedings
Band
6099
Seite
89-101
Konferenz
5th International Conference, FUN 2010
Konferenzort
Ischia, Italy
Konferenzdatum
2010-06-02 – 2010-06-04
PUB-ID

Zitieren

Burcsi P, Cicalese F, Fici G, Lipták Z. On Table Arrangements, Scrabble Freaks, and Jumbled Pattern Matching. In: Boldi P, ed. Fun with Algorithms: 5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010. Proceedings. Lecture Notes in Computer Science. Vol 6099. Berlin, Heidelberg: Springer; 2010: 89-101.
Burcsi, P., Cicalese, F., Fici, G., & Lipták, Z. (2010). On Table Arrangements, Scrabble Freaks, and Jumbled Pattern Matching. In P. Boldi (Ed.), Lecture Notes in Computer Science: Vol. 6099. Fun with Algorithms: 5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010. Proceedings (pp. 89-101). Berlin, Heidelberg: Springer. doi:10.1007/978-3-642-13122-6_11
Burcsi, P., Cicalese, F., Fici, G., and Lipták, Z. (2010). “On Table Arrangements, Scrabble Freaks, and Jumbled Pattern Matching” in Fun with Algorithms: 5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010. Proceedings, Boldi, P. ed. Lecture Notes in Computer Science, vol. 6099, (Berlin, Heidelberg: Springer), 89-101.
Burcsi, P., et al., 2010. On Table Arrangements, Scrabble Freaks, and Jumbled Pattern Matching. In P. Boldi, ed. Fun with Algorithms: 5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010. Proceedings. Lecture Notes in Computer Science. no.6099 Berlin, Heidelberg: Springer, pp. 89-101.
P. Burcsi, et al., “On Table Arrangements, Scrabble Freaks, and Jumbled Pattern Matching”, Fun with Algorithms: 5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010. Proceedings, P. Boldi, ed., Lecture Notes in Computer Science, vol. 6099, Berlin, Heidelberg: Springer, 2010, pp.89-101.
Burcsi, P., Cicalese, F., Fici, G., Lipták, Z.: On Table Arrangements, Scrabble Freaks, and Jumbled Pattern Matching. In: Boldi, P. (ed.) Fun with Algorithms: 5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010. Proceedings. Lecture Notes in Computer Science. 6099, p. 89-101. Springer, Berlin, Heidelberg (2010).
Burcsi, Péter, Cicalese, Ferdinando, Fici, Gabriele, and Lipták, Zsuzsanna. “On Table Arrangements, Scrabble Freaks, and Jumbled Pattern Matching”. Fun with Algorithms: 5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010. Proceedings. Ed. Paolo Boldi. Berlin, Heidelberg: Springer, 2010.Vol. 6099. Lecture Notes in Computer Science. 89-101.

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Suchen in

Google Scholar
ISBN Suche