Amihood Amir
Abstract
In this article, we address a new version of dynamic pattern matching. The dynamic text and static pattern matching problem is the problem of finding a static pattern in a text that is continuously being updated. The goal is to report all new occurrences of the pattern in the text after each text update. We present an algorithm for solving the problem where the text update operation is changing the symbol value of a text location. Given a text of length n and a pattern of length m, our algorithm preprocesses the text in time O(n log log m), and the pattern in time O(m log m). The extra space used is O(n + m log m). Following each text update, the algorithm deletes all prior occurrences of the pattern that no longer match, and reports all new occurrences of the pattern in the text in O(log log m) time. We note that the complexity is not proportional to the number of pattern occurrences, since all new occurrences can be reported in a succinct form.
- Alon, N., and Naor, M. 1996. Derandomization, witnesses for boolean matrix multiplication and construction of perfect hash functions. Algorithmica 16, 4-5, 434--449.Google Scholar
Cross Ref
- Alstrup, S., Brodal, G. S., and Rauhe, T. 2000. Pattern matching in dynamic texts. In Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 819--828. Google ScholarDigital Library
- Beame, P., and Fich, F. E. 2002. Optimal bounds for the predecessor problem and related problems. J. Comput. Syst. Sci. 65, 1, 38--72. Google ScholarDigital Library
- Berkman, O., and Vishkin, U. 1994. Finding level-ancestors in trees. J. Comput. Syst. Sci. 48, 2, 214--229. Google ScholarDigital Library
- Buchsbaum, A. L. 2006. Personal communication.Google Scholar
- Buchsbaum, A. L., Goodrich, M. T., and Westbrook, J. 2000. Range searching over tree cross products. In Proceedings of the 8th Annual European Symposium on Algorithms (ESA). Springer Verlag, Berlin. 120--131. Google ScholarDigital Library
- Cole, R., and Harihan, R. 1997. Tighter bounds on the exact complexity of string matching. SIAM J. Comput. 26, 3, 803--856. Google ScholarDigital Library
- Farach, M. 1997. Optimal suffix tree construction with large alphabets. In Proceedings of the 38th IEEE Symposium on Foundations of Computer Science (FOCS). 137--143. Google ScholarDigital Library
- Farach, M., and Muthukrishnan, S. 1996. Perfect hashing for strings: Formalization and algorithms. In Proceedings of the 7th Symposium on Combinatorial Pattern Matching (CPM). Springer Verlag, Berlin. 130--140. Google ScholarDigital Library
- Ferragina, P., and Grossi, R. 1995. Fast incremental text editing. In Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms (SODA). 531--540. Google ScholarDigital Library
- Gabow, H. N., Bentley, J. L., and Tarjan, R. E. 1984. Scaling and related techniques for geometry problems. In Proceedings of the 16th ACM Symposium on Theory of Computing (STOC), vol. 67. 135--143. Google ScholarDigital Library
- Gu, M., Farach, M., and Beigel, R. 1994. An efficient algorithm for dynamic text indexing. In Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms (SODA). 697--704. Google ScholarDigital Library
- Hagerup, T., Miltersen, P. B., and Pagh, R. 2001. Deterministic dictionaries. J. Alg. 41, 1, 69--85. Google ScholarDigital Library
- Harel, D., and Tarjan, R. 1984. Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13, 2, 338--355. Google ScholarDigital Library
- Kärkkäinen, J., and Sanders, P. 2003. Simple linear work suffix array construction. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 2719. Springer Verlag, Berlin. 943--955.Google ScholarDigital Library
- Knuth, D., Morris, J., and Pratt, V. 1977. Fast pattern matching in strings. SIAM J. Comput. 6, 323--350.Google ScholarDigital Library
- Landau, G. M., and Vishkin, U. 1988. Fast string matching with k differences. J. Comput. Syst. Sci. 37, 1, 63--78. Google ScholarDigital Library
- Landau, G. M., and Vishkin, U. 1994. Pattern matching in a digitized image. Algorithmica 12, 4-5, 375--408.Google ScholarCross Ref
- Levenshtein, V. I. 1966. Binary codes capable of correcting, deletions, insertions and reversals. Soviet Phys. Dokl. 10, 707--710.Google Scholar
- Lowrance, R., and Wagner, R. A. 1975. An extension of the string-to-string correction problem. J. ACM 22, 2, 177--183. Google ScholarDigital Library
- McCreight, E. M. 1976. A space-economical suffix tree construction algorithm. J. ACM 23, 262--272. Google ScholarDigital Library
- Sahinalp, S. C., and Vishkin, U. 1996. Efficient approximate and dynamic matching of patterns using a labeling paradigm. In Proceedings of the 37th IEEE Symposium on Foundations of Computer Science (FOCS). 320--328. Google ScholarDigital Library
- Schieber, B., and Vishkin, U. 1988. On finding lowest common ancestors: Simplification and parallelization. SIAM J. Comput. 17, 6, 1253--1262. Google ScholarDigital Library
- Smith, T., and Waterman, M. 1981. Identification of common molecular subsequences. J. Mol. Biol. 147, 195--197.Google ScholarCross Ref
- Ukkonen, E. 1995. On-Line construction of suffix trees. Algorithmica 14, 249--260.Google ScholarDigital Library
- van Emde Boas, P. 1974. An O(n log log n) online algorithm for the insert-extract min problem. Tech. Rep. TR 74-221, Cornell University, Department of Computer Science. Google ScholarDigital Library
- Weiner, P. 1973. Linear pattern matching algorithm. In Proceedings of the 14th IEEE Symposium on Switching and Automata Theory. 1--11.Google ScholarDigital Library
- Willard, D. E. 1983. Log-Logarithmic worst-case range queries are possible in space Theta(n). Inf. Process. Lett. 17, 2, 81--84.Google ScholarCross Ref
Index Terms
- Dynamic text and static pattern matching
Recommendations
Approximate pattern matching with k-mismatches in packed text
Given strings P of length m and T of length n over an alphabet of size @s, the string matching with k-mismatches problem is to find the positions of all the substrings in T that are at Hamming distance at most k from P. If T can be read only one ...
Fast pattern matching for entropy bounded text
DCC '95: Proceedings of the Conference on Data CompressionWe present the first known case of one-dimensional and two-dimensional string matching algorithms for text with bounded entropy. Let n be the length of the text and m be the length of the pattern. We show that the expected complexity of the algorithms ...
Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions
SFCS '93: Proceedings of the 1993 IEEE 34th Annual Foundations of Computer ScienceAll algorithms below are optimal alphabet-independent parallel CRCW PRAM algorithms. In one dimension: Given a pattern string of length m for the string-matching problem, we design an algorithm that computes a deterministic sample of a sufficiently long ...
Comments