|
|||||
|
|
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 等数据库收录！ | |