Two-dimensional maximal repetitions

Autor: Amihood Amir, Gad M. Landau, Shoshana Marcus, Dina Sokol

Publikováno v: Theoretical Computer Science. 812:49-61

Maximal repetitions or runs in strings have a wide array of applications and thus have been extensively studied. In this paper, we extend this notion to 2-dimensions, precisely defining a maximal 2D repetition. We provide initial bounds on the number

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::5e8154e054ada0160f9242b64f45b17f
https://doi.org/10.1016/j.tcs.2019.07.006

Lower Bounds for the Number of Repetitions in 2D Strings

Autor: Gad M. Landau, Samah Ghazawi, Paweł Gawrychowski

Publikováno v: String Processing and Information Retrieval ISBN: 9783030866914
SPIRE

A 2D string is simply a 2D array. We continue the study of the combinatorial properties of repetitions in such strings over the binary alphabet, namely the number of distinct tandems, distinct quartics, and runs. First, we construct an infinite famil

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::987c6173e1fef29812196b6fddf4d0e7
https://doi.org/10.1007/978-3-030-86692-1_15

Period recovery of strings over the Hamming and edit distances

Autor: Amihood Amir, Dina Sokol, Gad M. Landau, Mika Amit

Publikováno v: Theoretical Computer Science. 710:2-18

A string T of length m is periodic in P of length p if P is a substring of T and T[i]=T[i+p] T [ i ] = T [ i + p ] for all 0≤i≤m−p−1 0 ≤ i ≤ m − p − 1 and m≥2p m ≥ 2 p . The shortest such prefix, P , is called the period of T (i.e

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::4d869c752700536c1243e967049f85b1
https://doi.org/10.1016/j.tcs.2017.10.026

String cadences

Autor: Amihood Amir, Alberto Apostolico, Travis Gagie, Gad M. Landau

Publikováno v: Theoretical Computer Science. 698:4-8

We say a string has a cadence if a certain character is repeated at regular intervals, possibly with intervening occurrences of that character. We call the cadence anchored if the first interval must be the same length as the others. We give a sub-qu

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c86810cc4848b425b4ffa5f6d98fd0f5
https://doi.org/10.1016/j.tcs.2017.04.019

Top Tree Compression of Tries

Autor: Oren Weimann, Gad M. Landau, Paweł Gawrychowski, Philip Bille, Inge Li Gørtz

Publikováno v: Bille, P, Gawrychowski, P, Gørtz, I L, Landau, G M & Weimann, O 2019, Top Tree Compression of Tries . in Proceedings of 30th International Symposium on Algorithms and Computation . Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, vol. 149, pp. 4:1--4:18, 30th International Symposium on Algorithms and Computation, Shanghai, China, 09/12/2019 . https://doi.org/10.4230/LIPIcs.ISAAC.2019.4
Bille, P, Gawrychowski, P, Gørtz, I L, Landau, G M & Weimann, O 2021, ' Top Tree Compression of Tries ', Algorithmica, vol. 83, no. 12, pp. 3602-3628 . https://doi.org/10.1007/s00453-021-00869-w

We present a compressed representation of tries based on top tree compression [ICALP 2013] that works on a standard, comparison-based, pointer machine model of computation and supports efficient prefix search queries. Namely, we show how to preproces

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5b0a811ea5715d12b6bda66a01172b94