## ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS

Burcsi P, Cicalese F, Fici G, Lipták Z (2012)
International Journal of Foundations of Computer Science 23(02): 357-374.

Zeitschriftenaufsatz | Veröffentlicht | Englisch

Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Burcsi, Peter; Cicalese, Ferdinando; Fici, Gabriele; Lipták, ZsuzsannaUniBi
Einrichtung
Abstract / Bemerkung
The Parikh vector p(s) of a string s over a finite ordered alphabet Sigma = {a(1), . . . , a(sigma)} is defined as the vector of multiplicities of the characters, p(s) = (p(1), . . . , p(sigma)), where p(i) = vertical bar{j vertical bar s(j) = a(i)}vertical bar. Parikh vector q occurs in s if s has a substring t with p(t) = q. The problem of searching for a query q in a text s of length n can be solved simply and worst-case optimally with a sliding window approach in O(n) time. We present two novel algorithms for the case where the text is fixed and many queries arrive over time. The first algorithm only decides whether a given Parikh vector appears in a binary text. It uses a linear size data structure and decides each query in O(1) time. The preprocessing can be done trivially in Theta(n(2)) time. The second algorithm finds all occurrences of a given Parikh vector in a text over an arbitrary alphabet of size sigma >= 2 and has sub-linear expected time complexity. More precisely, we present two variants of the algorithm, both using an O(n) size data structure, each of which can be constructed in O(n) time. The first solution is very simple and easy to implement and leads to an expected query time of O(n(sigma/log sigma)(1/2) log m/root m), where m = Sigma(i) q(i) is the length of a string with Parikh vector q. The second uses wavelet trees and improves the expected runtime to O(n(sigma/log sigma)(1/2) 1 root m), i.e., by a factor of log m.
Stichworte
string algorithms; pattern matching; Parikh vectors; permuted strings; average case analysis
Erscheinungsjahr
2012
Zeitschriftentitel
International Journal of Foundations of Computer Science
Band
23
Ausgabe
02
Seite(n)
357-374
ISSN
0129-0541
eISSN
1793-6373
Page URI
https://pub.uni-bielefeld.de/record/2493233

## Zitieren

Burcsi P, Cicalese F, Fici G, Lipták Z. ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS. International Journal of Foundations of Computer Science. 2012;23(02):357-374.
Burcsi, P., Cicalese, F., Fici, G., & Lipták, Z. (2012). ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS. International Journal of Foundations of Computer Science, 23(02), 357-374. doi:10.1142/S0129054112400175
Burcsi, Peter, Cicalese, Ferdinando, Fici, Gabriele, and Lipták, Zsuzsanna. 2012. “ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS”. International Journal of Foundations of Computer Science 23 (02): 357-374.
Burcsi, P., Cicalese, F., Fici, G., and Lipták, Z. (2012). ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS. International Journal of Foundations of Computer Science 23, 357-374.
Burcsi, P., et al., 2012. ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS. International Journal of Foundations of Computer Science, 23(02), p 357-374.
P. Burcsi, et al., “ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS”, International Journal of Foundations of Computer Science, vol. 23, 2012, pp. 357-374.
Burcsi, P., Cicalese, F., Fici, G., Lipták, Z.: ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS. International Journal of Foundations of Computer Science. 23, 357-374 (2012).
Burcsi, Peter, Cicalese, Ferdinando, Fici, Gabriele, and Lipták, Zsuzsanna. “ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS”. International Journal of Foundations of Computer Science 23.02 (2012): 357-374.
Export

Open Data PUB

### Web of Science

Dieser Datensatz im Web of Science®
Quellen

arXiv: 1102.1746

Suchen in