Finding Patterns In Given Intervals

• Autorzy: Crochemore M. , Iliopoulos C.S. , Kubica M. , Rahman M.S. , Waleń T.
• Języki publikacji: EN

Abstrakty

EN

In this paper, we study the pattern matching problem in given intervals. Depending on whether the intervals are given a priori for pre-processing, or during the query along with the pattern or, even in both the cases, we develop efficient solutions for different variants of this problem. In particular, we present efficient indexing schemes for each of the above variants of the problem.

Słowa kluczowe

EN

algorithms; data structures; pattern matching; string

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 101, nr 3
• Strony: 173--186
• Opis fizyczny: Bibliogr. 43 poz., tab.

Twórcy

autor

Crochemore M.

autor

Iliopoulos C.S.

autor

Kubica M.

autor

Rahman M.S.

autor

Waleń T.

• AlEDA Group, Department of CSE, BUET, Dhaka-1000, Bangladesh,

Bibliografia

• [1] Agarwal, P. K., Govindarajan, S., Muthukrishnan, S.: Range Searching in Categorical Data: Colored Range Searching on Grid., ESA (R. H. Möhring, R. Raman, Eds.), 2461, Springer, 2002, ISBN 3-540-44180-8.
• [2] Amir, A., Aumann, Y., Benson, G., Levy, A., Lipsky, O., Porat, E., Skiena, S., Vishne, U.: Pattern matching with address errors: rearrangement distances., SODA, ACM Press, 2006, ISBN 0-89871-605-5.
• [3] Amir, A., Butman, A., Crochemore,M., Landau, G.M., Schaps,M.: Two-dimensional pattern matching with rotations., Theor. Comput. Sci., 314(1-2), 2004, 173-187.
• [4] Amir, A., Butman, A., Lewenstein, M.: Real Scaled Matching., Inf. Process. Lett., 70(4), 1999, 185-190.
• [5] Amir, A., Chencinski, E.: Faster Two Dimensional Scaled Matching., CPM (M. Lewenstein, G. Valiente, Eds.), 4009, Springer, 2006, ISBN 3-540-35455-7.
• [6] Amir, A., Chencinski, E., Iliopoulos, C., Kopelowitz, T., Zhang, H.: PropertyMatching andWeightedMatching, CPM, 2006.
• [7] Amir, A., Kapah, O., Tsur, D.: Faster Two Dimensional Pattern Matching with Rotations., CPM (S. C. Sahinalp, S. Muthukrishnan, U. Dogrusöz, Eds.), 3109, Springer, 2004, ISBN 3-540-22341-X.
• [8] Apostolico, A.: The Myriad Virtues of Subword Trees, Combinatorial Algorithms on Words, NATO ISI Series, Springer-verlag, 1985.
• [9] Bender, M. A., Farach-Colton, M.: The LCA Problem Revisited., Latin American Theoretical Informatics (LATIN), 2000.
• [10] Berkman, O., Breslauer, D., Galil, Z., Schieber, B., Vishkin, U.: Highly Parallelizable Problems (Extended Abstract), STOC, ACM, 1989.
• [11] Butman, A., Eres, R., Landau, G. M.: Scaled and permuted string matching., Inf. Process. Lett., 92(6), 2004, 293-297.
• [12] Cole, R., Gottlieb, L.-A., Lewenstein, M.: Dictionary matching and indexing with errors and don't cares., STOC (L. Babai, Ed.), ACM, 2004, ISBN 1-58113-852-0.
• [13] Cole, R., Hariharan, R.: Verifying candidate matches in sparse and wildcard matching., STOC, 2002.
• [14] Crochemore, M., Iliopoulos, C. S., Kubica, M., Rahman, M. S., Walen, T.: Improved Algorithms for the Range Next Value Problem and Applications, STACS (S. Albers, P. Weil, C. Rochange, Eds.), 08001, Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany, 2008.
• [15] Crochemore, M., Iliopoulos, C. S., Rahman, M. S.: Finding Patterns in Given Intervals, MFCS (L. Kucera, A. Kucera, Eds.), 4708, Springer, 2007, ISBN 978-3-540-74455-9.
• [16] Crochemore, M., Iliopoulos, C. S., Rahman, M. S.: Optimal Prefix and Suffix Queries on Texts., AofA (P. Jacquet, Ed.), AH, DMTCS Proceedings, 2007.
• [17] Crochemore,M., Rytter, W.: Jewels of Stringology, World Scientific, 2002.
• [18] Farach, M.: Optimal Suffix Tree Construction with Large Alphabets., FOCS, 1997.
• [19] Fischer, M., Paterson, M.: String matching and other Products, in Complexity of Computation, R.M. Karp (editor), SIAM AMS Proceedings, 7, 1974, 113-125.
• [20] Flouri, T., Iliopoulos, C. S., Rahman, M. S., Vagner, L., Vor´acek, M.: Indexing Factors in DNA/RNA sequences., BIRD08-ALBIO08, 2008, Lecture Notes in Bioinformatics, 436-445.
• [21] Gabow, H., Bentley, J., Tarjan, R.: Scaling and Related Techniques for Geometry Problems, Symposium on the Theory of Computing (STOC), 1984.
• [22] Gusfield, D.: Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology, Cambridge University Press, 1997, ISBN 0-521-58519-8.
• [23] Harel, D., Tarjan, R. E.: Fast Algorithms for Finding Nearest Common Ancestors., SIAM J. Comput., 13(2), 1984, 338-355.
• [24] Hirschberg, D. S.: Algorithms for the Longest Common Subsequence Problem., J. ACM, 24(4), 1977, 664-675.
• [25] Hunt, J. W., Szymanski, T. G.: A Fast Algorithm for Computing Longest Subsequences., Commun. ACM, 20(5), 1977, 350-353.
• [26] Iliopoulos, C. S., Mouchard, L., Rahman, M. S.: A New Approach to Pattern Matching in Degenerate DNA/RNA Sequences and Distributed Pattern Matching, Mathematics in Computer Science, 1(4), 2008, 557-569.
• [27] Iliopoulos, C. S., Rahman, M. S.: Faster index for property matching, Inf. Process. Lett., 105(6), 2008, 218-223.
• [28] Iliopoulos, C. S., Rahman, M. S.: Indexing Factors with Gaps, Algorithmica, 55(1), 2009, 60-70.
• [29] Iliopoulos, C. S., Rahman, M. S.: A New Efficient Algorithm for Computing the Longest Common Subsequence, Theory Comput. Syst., 45(2), 2009, 355-371.
• [30] Johannes Fischer, V. H.: A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array., ESCAPE (B. Chen, G. Zhang, Eds.), 4614, Springer, 2007.
• [31] Jurka, J.: Human repetitive elements., in: Molecular Biology and Biotechnology. (R. A. Meyers, Ed.).
• [32] Jurka, J.: Origin and evolution of Alu repetitive elements., in: The impact of short interspersed elements (SINEs) on the host genome. (R. Maraia, Ed.).
• [33] Levenshtein, V.: Binary Codes Capable of Correcting, Deletions, Insertions and Reversals, Soviet Phys. Dokl., 10, 1966, 707-710.
• [34] Mäkinen, V., Navarro, G.: Position-Restricted Substring Searching, LATIN, 2006.
• [35] McCreight, E.M.: A Space-Economical Suffix Tree Construction Algorithm., J. ACM, 23(2), 1976, 262-272.
• [36] Rahman, M. S., Iliopoulos, C., Lee, I., Mohamed, M., Smyth, W.: Finding Patterns with Variable Length Gaps or Don't Cares., COCOON (D. Chen, D. Lee, Eds.), 4112, Springer, 2006.
• [37] Rahman, M. S., Iliopoulos, C. S.: Indexing Factors with Gaps., SOFSEM (J. van Leeuwen, G. F. Italiano, W. van der Hoek, C. Meinel, H. Sack, F. Plasil, Eds.), 4362, Springer, 2007, ISBN 978-3-540-69506-6.
• [38] Rahman, M. S., Iliopoulos, C. S.: A New Efficient Algorithm for Computing the Longest Common Subsequence., AAIM (M.-Y. Kao, X.-Y. Li, Eds.), 4508, Springer, 2007, ISBN 978-3-540-72868-9.
• [39] Rahman, M. S., Iliopoulos, C. S.: Pattern Matching Algorithms with Don't Cares., SOFSEM (2) (J. van Leeuwen, G. F. Italiano, W. van der Hoek, C. Meinel, H. Sack, F. Plasil, M. Bielikov´a, Eds.), Institute of Computer Science AS CR, Prague, 2007, ISBN 80-903298-9-6.
• [40] Rahman, M. S., Iliopoulos, C. S., Mouchard, L.: Pattern Matching in Degenerate DNA/RNA Sequences., WALCOM, 2007.
• [41] Sadakane, K.: Succinct Data Structures for Flexible Text Retrieval Systems., Journal of Discrete Algorithms, 5(1), 2007, 12-22.
• [42] Schieber, B., Vishkin, U.: On Finding Lowest Common Ancestors: Simplification and Parallelization, SIAM J. Comput., 17(6), 1988, 1253-1262.
• [43] Ukkonen, E.: On-Line Construction of Suffix Trees., Algorithmica, 14(3), 1995, 249-260.