Simple deterministic wildcard matching. (English) Zbl 1185.68830
Summary: We present a simple and fast deterministic solution to the string matching with don’t cares problem. The task is to determine all positions in a text where a pattern occurs, allowing both pattern and text to contain single character wildcards. Our algorithm takes \(O(n\log m)\) time for a text of length \(n\) and a pattern of length \(m\) and in our view the algorithm is conceptually simpler than previous approaches.
MSC:
| 68W05 | Nonnumerical algorithms |
References:
| [1] | R. Cole, R. Hariharan, Verifying candidate matches in sparse and wildcard matching, in: Proceedings of the Annual ACM Symposium on Theory of Computing, 2002, pp. 592-601; R. Cole, R. Hariharan, Verifying candidate matches in sparse and wildcard matching, in: Proceedings of the Annual ACM Symposium on Theory of Computing, 2002, pp. 592-601 · Zbl 1192.68819 |
| [2] | M. Fischer, M. Paterson, String matching and other products, in: R. Karp (Ed.), Proceedings of the 7th SIAM-AMS Complexity of Computation, 1974, pp. 113-125; M. Fischer, M. Paterson, String matching and other products, in: R. Karp (Ed.), Proceedings of the 7th SIAM-AMS Complexity of Computation, 1974, pp. 113-125 · Zbl 0301.68027 |
| [3] | P. Indyk, Faster algorithms for string matching problems: Matching the convolution bound, in: Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1998, pp. 166-173; P. Indyk, Faster algorithms for string matching problems: Matching the convolution bound, in: Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1998, pp. 166-173 |
| [4] | Kalai, A., Efficient pattern-matching with don’t cares, (Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (2002), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA), 655-656 · Zbl 1093.68674 |
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.
