Simple Deterministic Wildcard Matching

Peter Clifford; Raphaël Clifford

doi:10.1016/j.ipl.2006.08.002

Simple Deterministic Wildcard Matching

Peter Clifford
, Raphaël Clifford

Algorithms and Complexity

Research output: Contribution to journal › Article (Academic Journal) › peer-review

86 Citations (Scopus)

Abstract

We present a simple and fast deterministic solution to the \emph{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 is conceptually simpler than previous approaches.

Translated title of the contribution	Simple Deterministic Wildcard Matching
Original language	English
Article number	-
Journal	Information Processing Letters
DOIs	https://doi.org/10.1016/j.ipl.2006.08.002
Publication status	Published - 2007

Access to Document

10.1016/j.ipl.2006.08.002

Handle.net

Persistent link

Cite this

@article{c9524a7ed13d4c11a44becdfd388c5fe,

title = "Simple Deterministic Wildcard Matching",

abstract = "We present a simple and fast deterministic solution to the \textbackslash{}emph\{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\textbackslash{}log\{m\})\$ time for a text of length \$n\$ and a pattern of length \$m\$ and in our view is conceptually simpler than previous approaches.",

author = "Peter Clifford and Rapha{\"e}l Clifford",

year = "2007",

doi = "10.1016/j.ipl.2006.08.002",

language = "English",

journal = "Information Processing Letters",

issn = "1872-6119",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Simple Deterministic Wildcard Matching

AU - Clifford, Peter

AU - Clifford, Raphaël

PY - 2007

Y1 - 2007

N2 - We present a simple and fast deterministic solution to the \emph{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 is conceptually simpler than previous approaches.

AB - We present a simple and fast deterministic solution to the \emph{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 is conceptually simpler than previous approaches.

U2 - 10.1016/j.ipl.2006.08.002

DO - 10.1016/j.ipl.2006.08.002

M3 - Article (Academic Journal)

SN - 1872-6119

JO - Information Processing Letters

JF - Information Processing Letters

M1 - -

ER -

Simple Deterministic Wildcard Matching

Abstract

Access to Document

Handle.net

Fingerprint

Cite this