A Novel Algorithm for String Matching with Mismatches

Vinod-prasad P.

2016

Abstract

We present an online algorithm to deal with pattern matching in strings. The problem we investigate is commonly known as ‘string matching with mismatches’ in which the objective is to report the number of characters that match when a pattern is aligned with every location in the text. The novel method we propose is based on the frequencies of individual characters in the pattern and the text. Given a pattern of length M, and the text of length N, both defined over an alphabet of size σ, the algorithm consumes O(M) space and executes in O(MN/σ) time on the average. The average execution time O(MN/σ) simplifies to O(N) for patterns of size M ≤ σ. The algorithm makes use of simple arrays, which reduces the cost overhead to maintain the complex data structures such as suffix trees or automaton.

Paper Citation

in Harvard Style

P. V. (2016). A Novel Algorithm for String Matching with Mismatches . In Proceedings of the 5th International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM, ISBN 978-989-758-173-1, pages 638-644. DOI: 10.5220/0005752006380644

in Bibtex Style

@conference{icpram16,
author={Vinod-prasad P.},
title={A Novel Algorithm for String Matching with Mismatches},
booktitle={Proceedings of the 5th International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM,},
year={2016},
pages={638-644},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005752006380644},
isbn={978-989-758-173-1},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 5th International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM,
TI - A Novel Algorithm for String Matching with Mismatches
SN - 978-989-758-173-1
AU - P. V.
PY - 2016
SP - 638
EP - 644
DO - 10.5220/0005752006380644