Simple deterministic wildcard matching |
| |
| Authors: | Peter Clifford |
| |
| Affiliation: | a Department of Statistics, University of Oxford, UK
b University of Bristol, Department of Computer Science, Merchant Venturers Building, Woodland Road, Bristol, BS8 1UB, UK |
| |
| Abstract: | 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(nlogm) 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. |
| |
| Keywords: | Algorithms String matching Wildcards |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
