Generalized and Weighted Strings: Repetitions and Pattern Matching

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F04%3A00109860" target="_blank" >RIV/68407700:21230/04:00109860 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Generalized and Weighted Strings: Repetitions and Pattern Matching

Original language description

Generalized and weighted strings are special strings capable of expressing variability and uncertainity of appearance of a symbol in a given position. These types of strings are mainly used in molecular biology. In this paper we present a finite state automata approach for solving various pattern matching problems. We present the Generalized Factor Automaton (GFA), a novel structure for indexing generalized strings. We show how to use GFA for substring searching and searching maximum repeating factors in generalized strings. Finally, we show how to transform the finite automaton for a given pattern matching problem on strings to an automaton for the pattern matching problem on generalized strings.

Czech name

—

Czech description

—

Type

C - Chapter in a specialist book

CEP classification

IN - Informatics

OECD FORD branch

—

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2004

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Book/collection name

Texts in Algorithmics, Volume 2 - String Algorithmics

ISBN

1-904987-02-8

Number of pages of the result

24

Pages from-to

225-248

Number of pages of the book

251

Publisher name

King's College

Place of publication

London

UT code for WoS chapter

—