Multi-Dimensional Pattern Matching with Dimensional Wildcards: Data Structures and Optimal On-Line Search Algorithms

Aho, 1990, Algorithms for finding pattern in strings A. Amir, G. Benson, Two-dimensional periodicity and its applications, Proceedings of ACM–SIAM Symposium on Discrete Algorithms, 1992, 440, 452 Amir, 1994, An alphabet independent approach to two-dimensional pattern matching, SIAM J. Comput., 23, 313, 10.1137/S0097539792226321 Apostolico, 1984, The myriad virtues of subword trees, 12, 85 Apostolico, 1988, Parallel construction of a suffix tree with applications, Algorithmica, 3, 347, 10.1007/BF01762122 Aho, 1974 Berkman, 1995, The subtree max gap problem with application to parallel string covering, Inform. and Comput., 123, 127, 10.1006/inco.1995.1162 Breslauer, 1995, Dictionary-matching on unbounded alphabets: Uniform length dictionaries, J. Algorithms, 18, 278, 10.1006/jagm.1995.1011 R. Cole, M. Crochemore, Z. Galil, L. Gasieniec, R. Hariharan, S. Muthukrishnan, K. Park, W. Rytter, 1993, Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions, Proceedings, 34th Symposium on Foundations of Computer Science, 248, 258, IEEE, New York Cole, 1988, The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time, Algorithmica, 3, 329, 10.1007/BF01762121 Cole, 1989, Faster optimal parallel prefix sums and list ranking, Inform. and Comput., 81, 334, 10.1016/0890-5401(89)90036-9 Fischer, 1980, Parallel prefix computation, Assoc. Comput. Mach., 27, 831, 10.1145/322217.322232 Fischer, 1974, String matching and other products, 113 Z. Galil, K. Park, 1992, A truly alphabet independent two-dimensional pattern matching algorithm, Proceedings, 33th Symposium on Foundations of Computer Science, 247, 256, IEEE, New York Giancarlo, 1993, An index data structure for matrices, with applications to fast two-dimensional pattern matching, 709 R. Giancarlo, R. Grossi, Parallel construction and query of suffix trees for two-dimensional matrices, Proceedings of the 5th ACM Symposium on Parallel Algorithms and Architectures, 1993, 86, 97 Giancarlo, 1994, Generalizations of the periodicity theorem of Fine and Wilf, 787 Hagerup, 1988, On saving space in parallel computation, Inform. Process. Lett., 29, 327, 10.1016/0020-0190(88)90233-5 Hagerup, 1992, The log-star revolution, 577 Hagerup, 1995, Fast deterministic processor allocation, J. Algorithms, 18, 629, 10.1006/jagm.1995.1023 R. Jain, 1992, Workshop Report on Visual Information Systems, National Science Foundation JáJá, 1992 R. Karp, R. Miller, A. Rosenberg, 1972, Rapid identification of repeated patterns in strings, arrays and trees, Proceedings 4th Symposium on Theory of Computing, 125, 136, Assoc. Comput. Mach. New York Karpinski, 1994, An alphabet independent optimal parallel search for three dimensional patterns, 807 Knuth, 1973 Knuth, 1977, Fast pattern matching in strings, SIAM J Comput., 6, 189, 10.1137/0206024 Lyndon, 1962, The equationam=bnpin a free group, Michigan Math. J., 9, 289, 10.1307/mmj/1028998766 Y. Matias, U. Vishkin, 1991, Converting high probability into nearly constant time—With applications to parallel hashing, Proceedings, 23rd Symposium on Theory of Computing, 307, 316, Assoc. Comput. Mach. New York McCreight, 1976, A space economical suffice tree construction algorithm, Assoc. Comput. Mach., 23, 262, 10.1145/321941.321946 E. M. Muthukrishnan, K. Palem, Highly efficient dictionary matching in parallel, Proceedings of the 5th ACM Symposium on Parallel Algorithms and Architectures, 1993, 69, 78 Regnier, 1993, A unifying look atd, 684 Rosenfeld, 1982 Schieber, 1988, On finding lowest common ancestors: Simplification and parallelization, SIAM J. Comput., 17, 1253, 10.1137/0217079 Sleator, 1983, A data structure for dynamic trees, J. Comput. System Sci., 26, 362, 10.1016/0022-0000(83)90006-5 Tarjan, 1985, Finding biconnected components and computing tree functions in logarithmic parallel time, SIAM J. Comput., 14, 862, 10.1137/0214061 Vishkin, 1991, Deterministic sampling—A new technique for fast pattern matching, SIAM J. Comput., 20, 303, 10.1137/0220002 P. Weiner, 1973, Linear pattern matching algorithms, Proceedings, 14th Symposium on Switching and Automata Theory, 1, 11, IEEE, New York