Back to Search
Start Over
Algorithms for Jumbled Pattern Matching in Strings
- Source :
- Int. J. Found. Comput. Sci. 23(2): 357-374 (2012)
- Publication Year :
- 2011
-
Abstract
- The Parikh vector p(s) of a string s is defined as the vector of multiplicities of the characters. Parikh vector q occurs in s if s has a substring t with p(t)=q. We present two novel algorithms for searching for a query q in a text s. One solves the decision problem over a binary text in constant time, using a linear size index of the text. The second algorithm, for a general finite alphabet, finds all occurrences of a given Parikh vector q and has sub-linear expected time complexity; we present two variants, which both use a linear size index of the text.<br />Comment: 18 pages, 9 figures; article accepted for publication in the International Journal of Foundations of Computer Science
- Subjects :
- Computer Science - Data Structures and Algorithms
F.2.2
J.3
Subjects
Details
- Database :
- arXiv
- Journal :
- Int. J. Found. Comput. Sci. 23(2): 357-374 (2012)
- Publication Type :
- Report
- Accession number :
- edsarx.1102.1746
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1142/S0129054112400175