A new string matching algorithm

Mustaq Ahmed; M. Kaykobad; Rezaul Alam Chowdhury

doi:10.1080/0020716031000087113

A new string matching algorithm

Mustaq Ahmed
, M. Kaykobad
, Rezaul Alam Chowdhury

Computer Science

Bangladesh University of Engineering and Technology

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

In this paper a new exact string-matching algorithm with sub-linear average case complexity has been presented. Unlike other sub-linear string-matching algorithms it never performs more than n text character comparisons while working on a text of length n. It requires only O(m + σ) extra pre-processing time and space, where m is the length of the pattern and σ is the size of the alphabet.

Original language	English
Pages (from-to)	825-834
Number of pages	10
Journal	International Journal of Computer Mathematics
Volume	80
Issue number	7
DOIs	https://doi.org/10.1080/0020716031000087113
State	Published - Jul 2003

Keywords

Boyer-Moore algorithm
Complexity
String matching

Access to Document

10.1080/0020716031000087113

Cite this

@article{e87dce35ec4649e4a2ccc8635c77c6f7,

title = "A new string matching algorithm",

abstract = "In this paper a new exact string-matching algorithm with sub-linear average case complexity has been presented. Unlike other sub-linear string-matching algorithms it never performs more than n text character comparisons while working on a text of length n. It requires only O(m + σ) extra pre-processing time and space, where m is the length of the pattern and σ is the size of the alphabet.",

keywords = "Boyer-Moore algorithm, Complexity, String matching",

author = "Mustaq Ahmed and M. Kaykobad and Chowdhury, \{Rezaul Alam\}",

year = "2003",

month = jul,

doi = "10.1080/0020716031000087113",

language = "English",

volume = "80",

pages = "825--834",

journal = "International Journal of Computer Mathematics",

issn = "0020-7160",

number = "7",

}

TY - JOUR

T1 - A new string matching algorithm

AU - Ahmed, Mustaq

AU - Kaykobad, M.

AU - Chowdhury, Rezaul Alam

PY - 2003/7

Y1 - 2003/7

N2 - In this paper a new exact string-matching algorithm with sub-linear average case complexity has been presented. Unlike other sub-linear string-matching algorithms it never performs more than n text character comparisons while working on a text of length n. It requires only O(m + σ) extra pre-processing time and space, where m is the length of the pattern and σ is the size of the alphabet.

AB - In this paper a new exact string-matching algorithm with sub-linear average case complexity has been presented. Unlike other sub-linear string-matching algorithms it never performs more than n text character comparisons while working on a text of length n. It requires only O(m + σ) extra pre-processing time and space, where m is the length of the pattern and σ is the size of the alphabet.

KW - Boyer-Moore algorithm

KW - Complexity

KW - String matching

UR - https://www.scopus.com/pages/publications/28244465157

U2 - 10.1080/0020716031000087113

DO - 10.1080/0020716031000087113

M3 - Article

AN - SCOPUS:28244465157

SN - 0020-7160

VL - 80

SP - 825

EP - 834

JO - International Journal of Computer Mathematics

JF - International Journal of Computer Mathematics

IS - 7

ER -

A new string matching algorithm

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this