On Abelian Longest Common Factor with and without RLE

• Autorzy: Grabowski S. , Kociumaka T. , Radoszewski J.

Identyfikatory

DOI

10.3233/FI-2018-1740

• Języki publikacji: EN

Abstrakty

EN

We consider the Abelian longest common factor problem in two scenarios: when input strings are uncompressed and are of length at most n, and when the input strings are run-length encoded and their compressed representations have size at most m. The alphabet size is denoted by σ. For the uncompressed problem, we show an O(n²/ log^1+1/σ n)-time and O(n)-space algorithm in the case of σ = O(1), making a non-trivial use of tabulation. For the RLE-compressed problem, we show two algorithms: one working in O(m²σ² log³m) time and O(m(σ²+log²m)) space, which employs line sweep, and one that works in O(m³) time and O(m) space that applies in a careful way a sliding-window-based approach. The latter improves upon the previously known O(nm²)-time and O(m⁴)-time algorithms that were recently developed by Sugimoto et al. (IWOCA 2017) and Grabowski (SPIRE 2017), respectively.

Słowa kluczowe

EN

Abelian longest common factor problem; jumbled pattern matching; run-length encoding; RLE

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 163, nr 3
• Strony: 225--244
• Opis fizyczny: Bibliogr. 27 poz., rys., tab.

Twórcy

autor

Grabowski S.

• Institute of Applied Computer Science, Łódź University of Technology, Łódź, Poland

autor

Kociumaka T.

• Institute of Informatics, University of Warsaw, Warsaw, Poland

autor

Radoszewski J.

• Institute of Informatics, University of Warsaw, Warsaw, Poland

Bibliografia

• [1] Agarwal PK, Arge L, Kaplan H, Molad E, Tarjan RE, Yi K. An Optimal Dynamic Data Structure for Stabbing-Semigroup Queries, SIAM Journal on Computing, 2012;41(1):104-127. URL https://doi.org/10.1137/10078791X.
• [2] Alatabbi A, Iliopoulos CS, Langiu A, Rahman MS. Algorithms for Longest Common Abelian Factors, International Journal of Foundations of Computer Science. 2016;27(5):529-544. URL https://doi.org/10.1142/S0129054116500143.
• [3] Amir A, Apostolico A, Hirst T, Landau GM, Lewenstein N, Rozenberg L. Algorithms for Jumbled Indexing, Jumbled Border and Jumbled Square on run-length encoded strings, Theoretical Computer Science, 2016;656:146-159. URL https://doi.org/10.1016/j.tcs.2016.04.030.
• [4] Amir A, Chan TM, Lewenstein M, Lewenstein N. On Hardness of Jumbled Indexing, Automata, Languages, and Programming, ICALP 2014, Part I (J. Esparza, P. Fraigniaud, T. Husfeldt, E. Koutsoupias, Eds.), LNCS vol 8572, Springer, 2014 pp. 114-125. ISBN-978-3-662-43947-0. doi:10.1007/978-3-662-43948-7_10.
• [5] Badkobeh G, Fici G, Kroon S, Lipták Z. Binary jumbled string matching for highly run-length compressible texts, Information Processing Letters, 2013;113(17):604-608. URL https://doi.org/10.1016/j.ipl.2013.05.007.
• [6] Badkobeh G, Gagie T, Grabowski S, Nakashima Y, Puglisi SJ, Sugimoto S. Longest Common Abelian Factors and Large Alphabets, String Processing and Information Retrieval, SPIRE 2016 (S. Inenaga, K. Sadakane, T. Sakai, Eds.), LNCS vol 9954, Springer 2016 pp. 254-259. doi:10.1007/978-3-319-46049-9_24.
• [7] Bentley JL. Decomposable Searching Problems, Information Processing Letters, 1979;8(5):244-251. URL https://doi.org/10.1016/0020-0190(79)90117-0.
• [8] Bremner D, Chan TM, Demaine ED, Erickson J, Hurtado F, Iacono J, Langerman S, Pǎtraşcu M, Taslakian P. Necklaces, Convolutions, and X + Y, Algorithmica, 2014;69(2):294-314. doi:10.1007/s00453-012-9734-3.
• [9] Burcsi P, Cicalese F, Fici G, Lipták Z. On Table Arrangements, Scrabble Freaks, and Jumbled Pattern Matching, Fun with Algorithms, FUN 2010 (P. Boldi, L. Gargano, Eds.), LNCS vol 6099, Springer, 2010 pp. 89-101, ISBN-978-3-642-13121-9. doi:10.1007/978-3-642-13122-6_11.
• [10] 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(2):357-374. URL https://doi.org/10.1142/S0129054112400175.
• [11] Chan TM, Lewenstein M. Clustered Integer 3SUM via Additive Combinatorics, 47th Annual ACM on Symposium on Theory of Computing, STOC 2015 (R. A. Servedio, R. Rubinfeld, Eds.), ACM, 2015, ISBN-978-1-4503-3536-2. doi:10.1145/2746539.2746568.
• [12] Cicalese F, Fici G, Lipták Z. Searching for Jumbled Patterns in Strings, Prague Stringology Conference 2009 (J. Holub, J. Žd’árek, Eds.), Prague Stringology Club, Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University in Prague, 2009 pp. 105-117, ISBN-978-80-01-04403-2. URL http://www.stringology.org/event/2009/p10.html.
• [13] Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on strings, Cambridge University Press, 2007, ISBN 978-0-521-84899-2. doi:10.1017/cbo9780511546853.
• [14] Cunha LFI, Dantas S, Gagie T, Wittler R, Kowada LAB, Stoye J. Fast and Simple Jumbled Indexing for Binary Run-Length Encoded Strings, Combinatorial Pattern Matching, CPM 2017 (J. Kärkkäinen, J. Radoszewski, W. Rytter, Eds.), LIPIcs vol 78, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2017 pp. 19:1-19:9. doi:10.4230/LIPIcs.CPM.2017.19.
• [15] Giaquinta E, Grabowski S. New algorithms for binary jumbled pattern matching, Information Processing Letters, 2013;113(14-16):538-542. URL https://doi.org/10.1016/j.ipl.2013.04.013.
• [16] Grabowski S. Regular Abelian Periods and Longest Common Abelian Factors on Run-Length Encoded Strings, String Processing and Information Retrieval, SPIRE 2017 (G. Fici, M. Sciortino, R. Venturini, Eds.), LNCS vol 10508, Springer, 2017 pp. 208-213. doi:10.1007/978-3-319-67428-5_17.
• [17] Han Y. Deterministic sorting in O(n log log n) time and linear space, Journal of Algorithms, 2004;50(1):96-105. doi:10.1016/j.jalgor.2003.09.001.
• [18] Han Y, Thorup M. Integer Sorting in O(nplog log n) Expected Time and Linear Space, 43rd Symposium on Foundations of Computer Science, FOCS 2002, IEEE Computer Society, 2002 pp. 135-144. ISBN-0-7695-1822-2. doi:10.1109/SFCS.2002.1181890.
• [19] Hermelin D, Landau GM, Rabinovich Y, Weimann O. Binary Jumbled Pattern Matching via All-Pairs Shortest Paths, 2014. URL http://arxiv.org/abs/1401.2065.
• [20] Kociumaka T, Radoszewski J, Rytter W. Efficient Indexes for Jumbled Pattern Matching with Constant-Sized Alphabet, Algorithmica, 2017;77(4):1194-1215. doi:10.1007/s00453-016-0140-0.
• [21] Kociumaka T, Radoszewski J, Wiśniewski B. Subquadratic-Time Algorithms for Abelian Stringology Problems, Mathematical Aspects of Computer and Information Sciences, MACIS 2015 (I. S. Kotsireas, S. M. Rump, C. K. Yap, Eds.), LNCS vol 9582, Springer, 2015 pp. 320-334. doi:10.1007/978-3-319-32859-1_27.
• [22] Kociumaka T, Radoszewski J, Wiśniewski B. Subquadratic-Time Algorithms for Abelian Stringology Problems, AIMS Medical Science, 2017;4(3):332-351. doi:10.3934/ms.2017.3.332.
• [23] Landau GM, Vishkin U. Efficient String Matching with k Mismatches, Theoretical Computer Science, 1986;43:239-249. URL https://doi.org/10.1016/0304-3975(86)90178-7.
• [24] Moosa TM, Rahman MS. Indexing permutations for binary strings, Information Processing Letters, 2010;110(18-19):795-798. URL https://doi.org/10.1016/j.ipl.2010.06.012.
• [25] Moosa TM, Rahman MS. Sub-quadratic time and linear space data structures for permutation matching in binary strings, Journal of Discrete Algorithms, 2012;10:5-9. URL https://doi.org/10.1016/j.jda.2011.08.003.
• [26] Sugimoto S, Noda N, Inenaga S, Bannai H, Takeda M. Computing Abelian String Regularities Based on RLE, Combinatorial Algorithms, IWOCA 2017 (L. Brankovic, J. Ryan, W. F. Smyth, Eds.), LNCS vol 10765, Springer, 2017 pp. 420-431. doi:10.1007/978-3-319-78825-8_34.
• [27] Thorup M. Equivalence between priority queues and sorting, Journal of the ACM, 2007;54(6):28. doi:10.1145/1314690.1314692.