×

Range LCP. (English) Zbl 1410.68414

Summary: In this paper, we define the Range LCP problem as follows. Preprocess a string \(S\), of length \(n\), to enable efficient solutions of the following query: Given \([i, j]\), \(0<i\leqslant j\leqslant n\), compute \(\max_{\ell,k \in [i..j]}\mathrm{LCP}(S_\ell,S_k)\), where \(\mathrm{LCP}(S_\ell, S_k)\) is the length of the longest common prefix of the suffixes of \(S\) starting at locations \(\ell\) and \(k\). This is a natural generalization of the classical LCP problem. We provide algorithms with the following complexities:
1.
Preprocessing Time: \(O(|S|)\), Space: \(O(|S|)\), Query Time: \(O(|j-i|\log\log n)\).
2.
Preprocessing Time: none, Space: \(O(|j-i|\log |j-i|)\), Query Time: \(O(|j-i|\log |j-i|)\). However, the query just gives the pairs with the longest LCP, not the LCP itself.
3.
Preprocessing Time: \(O(|S| \log^2 |S|)\), Space: \(O(|S| \log^{1+\varepsilon}|S|)\) for arbitrary small constant \(\varepsilon\), Query Time: \(O(\log\log |S|)\).

MSC:

68W32 Algorithms on strings
68P05 Data structures
68W40 Analysis of algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Apostolico, A.; Preparata, F. P., Optimal off-line detection of repetitions in a string, Theor. Comput. Sci., 22, 297-315 (1983) · Zbl 0497.68052
[2] Bender, M. A.; Farach-Colton, M., The LCA problem revisited, (LATIN (2000)), 88-94 · Zbl 0959.68133
[3] Berkman, O.; Breslauer, D.; Galil, Z.; Schieber, B.; Vishkin, U., Highly parallelizable problems, (Proc. 21st ACM Symposium on Theory of Computation (1989)), 309-319
[4] Chan, T. M.; Larsen, K. G.; Pǎtraşcu, M., Orthogonal range searching on the ram, revisited, (Proc. 27th ACM Symposium on Computational Geometry. Proc. 27th ACM Symposium on Computational Geometry, (SoCG) (2011)), 1-10 · Zbl 1283.68139
[5] Cormode, G.; Muthukrishnan, S., Substring compression problems, (Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms. Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA) (2005)), 321-330 · Zbl 1297.68278
[6] Farach, M., Optimal suffix tree construction with large alphabets, (Proc. 38th IEEE Symposium on Foundations of Computer Science (1997)), 137-143
[7] Harel, D.; Tarjan, R. E., Fast algorithms for finding nearest common ancestor, J. Comput. Syst. Sci., 13, 338-355 (1984) · Zbl 0535.68022
[8] Iacono, J.; Özkan, O., Mergeable dictionaries, (Proc. 37th International Colloquium on Automata, Languages and Programming (ICALP), vol. 1. Proc. 37th International Colloquium on Automata, Languages and Programming (ICALP), vol. 1, Lect. Notes Comput. Sci., vol. 6198 (2010), Springer), 164-175 · Zbl 1287.68030
[9] Ilie, L.; Tinta, L., Practical algorithms for the longest common extension problem, (Proc. 16th International Symposium on String Processing and Information Retrieval. Proc. 16th International Symposium on String Processing and Information Retrieval, (SPIRE). Proc. 16th International Symposium on String Processing and Information Retrieval. Proc. 16th International Symposium on String Processing and Information Retrieval, (SPIRE), Lect. Notes Comput. Sci., vol. 5721 (2009), Springer), 302-309
[10] Kärkkäinen, J.; Sanders, P., Simple linear work suffix array construction, (Proc. 30th International Colloquium on Automata, Languages and Programming. Proc. 30th International Colloquium on Automata, Languages and Programming, (ICALP). Proc. 30th International Colloquium on Automata, Languages and Programming. Proc. 30th International Colloquium on Automata, Languages and Programming, (ICALP), Lect. Notes Comput. Sci., vol. 2719 (2003)), 943-955 · Zbl 1039.68042
[11] Kasai, T.; Lee, G.; Arimura, H.; Arikawa, S.; Park, K., Linear-time longest-common-prefix computation in suffix arrays and its applications, (Proc. 12th Symposium on Combinatorial Pattern Matching. Proc. 12th Symposium on Combinatorial Pattern Matching, (CPM) (2001)), 181-192 · Zbl 0990.68639
[12] Keller, O.; Kopelowitz, T.; Landau, S.; Lewenstein, M., Generalized substring compression, (Proc. 20th Annual Symposium on Combinatorial Pattern Matching (CPM) (2009), Springer), 26-38
[13] Landau, G. M.; Vishkin, U., Efficient string matching in the presence of errors, (Proc. 26th IEEE FOCS (1985)), 126-136
[14] Landau, G. M.; Vishkin, U., Fast parallel and serial approximate string matching, J. Algorithms, 10, 2, 157-169 (1989) · Zbl 0685.68033
[15] Lempel, A.; Ziv, J., On the complexity of finite sequences, IEEE Trans. Inf. Theory, 22, 75-81 (1976) · Zbl 0337.94013
[16] McCreight, E. M., A space-economical suffix tree construction algorithm, J. ACM, 23, 262-272 (1976) · Zbl 0329.68042
[17] Ukkonen, E., On-line construction of suffix trees, Algorithmica, 14, 249-260 (1995) · Zbl 0831.68027
[18] van Emde Boas, P.; Kaas, R.; Zijlstra, E., Design and implementation of an efficient priority queue, Math. Syst. Theory, 10, 99-127 (1977) · Zbl 0363.60104
[19] Weiner, P., Linear pattern matching algorithm, (Proc. 14th IEEE Symposium on Switching and Automata Theory (1973)), 1-11
[20] Yuan, H.; Atallah, M. J., Data structures for range minimum queries in multidimensional arrays, (Proc. 21st ACM-SIAM Symposium on Discrete Algorithms. Proc. 21st ACM-SIAM Symposium on Discrete Algorithms, (SODA) (2010)), 150-160 · Zbl 1288.68055
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.