Circular string matching revisited

Carl Barton; Costas S. Iliopoulos; Solon P. Pissis

Circular string matching revisited

Carl Barton, Costas S. Iliopoulos, Solon P. Pissis

Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference paper

Abstract

Circular string matching is a problem which naturally arises in many biological contexts. It consists in finding all occurrences of the rotations of a pattern of length m in a text of length n. There exist optimal average-case algorithms for exact circular string matching. In this article, we present a suboptimal average-case algorithm for exact circular string matching requiring time and space O(n). However, we anticipate that this can be easily adapted to deal with approximate circular string matching with k-mismatches, under the Hamming distance model, with no additional cost in time or space complexity for moderate values of k.

Original language	English
Title of host publication	Proceedings of the 14th Italian Conference on Theoretical Computer Science
Subtitle of host publication	ICTCS 2013
Pages	201-206
Number of pages	6
Publication status	Published - 2013

Access to Document

http://fmt.isti.cnr.it/~mtbeek/ICTCS13_Proceedings.pdf

Cite this

@inbook{8cc04a0bd2264db49fee9d03b91b740a,

title = "Circular string matching revisited",

abstract = "Circular string matching is a problem which naturally arises in many biological contexts. It consists in finding all occurrences of the rotations of a pattern of length m in a text of length n. There exist optimal average-case algorithms for exact circular string matching. In this article, we present a suboptimal average-case algorithm for exact circular string matching requiring time and space O(n). However, we anticipate that this can be easily adapted to deal with approximate circular string matching with k-mismatches, under the Hamming distance model, with no additional cost in time or space complexity for moderate values of k.",

author = "Carl Barton and Iliopoulos, {Costas S.} and Pissis, {Solon P.}",

year = "2013",

language = "English",

pages = "201--206",

booktitle = "Proceedings of the 14th Italian Conference on Theoretical Computer Science",

}

TY - CHAP

T1 - Circular string matching revisited

AU - Barton, Carl

AU - Iliopoulos, Costas S.

AU - Pissis, Solon P.

PY - 2013

Y1 - 2013

N2 - Circular string matching is a problem which naturally arises in many biological contexts. It consists in finding all occurrences of the rotations of a pattern of length m in a text of length n. There exist optimal average-case algorithms for exact circular string matching. In this article, we present a suboptimal average-case algorithm for exact circular string matching requiring time and space O(n). However, we anticipate that this can be easily adapted to deal with approximate circular string matching with k-mismatches, under the Hamming distance model, with no additional cost in time or space complexity for moderate values of k.

AB - Circular string matching is a problem which naturally arises in many biological contexts. It consists in finding all occurrences of the rotations of a pattern of length m in a text of length n. There exist optimal average-case algorithms for exact circular string matching. In this article, we present a suboptimal average-case algorithm for exact circular string matching requiring time and space O(n). However, we anticipate that this can be easily adapted to deal with approximate circular string matching with k-mismatches, under the Hamming distance model, with no additional cost in time or space complexity for moderate values of k.

M3 - Conference paper

SP - 201

EP - 206

BT - Proceedings of the 14th Italian Conference on Theoretical Computer Science

ER -

Circular string matching revisited

Abstract

Access to Document

Fingerprint

Cite this