King's College London

Research portal

Fast Average-Case Pattern Matching on Weighted Sequences

Research output: Contribution to journalArticle

Original languageEnglish
Pages (from-to)1331-1343
Number of pages13
JournalINTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Volume29
Issue number8
DOIs
Publication statusPublished - 1 Dec 2018

King's Authors

Abstract

A weighted string is a string in which a set of letters may occur at each position with respective occurrence probabilities. Weighted strings, also known as position weight matrices, weighted sequences or uncertain sequences, naturally arise in many contexts. In this paper, we study the problem of weighted string matching with a special focus on average-case analysis. Given a weighted pattern string x of length m, a text string y of length n > m, both on a constant-sized alphabet of size σ, and a cumulative weight threshold 1/z, defined as the minimal probability of occurrence of factors in a weighted string, we present an on-line algorithm requiring average-case search time o(n) for pattern matching for weight ratio z m <min{1 2log z+ 1 z, log σ log z(log m+loglog σ)}. For a pattern string x of length m, a weighted text string y of length n > m, both on a constant-sized alphabet, and a cumulative weight threshold 1/z, we present an on-line algorithm requiring average-case search time o(n) for the same weight ratio. The importance of these algorithms lies on the fact that, for these ratios, they can work in sublinear search time in the size of the input text, and in linear preprocessing costs in the size of the pattern.

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454