On left and right seeds of a string

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F12%3A00200725" target="_blank" >RIV/68407700:21240/12:00200725 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.jda.2012.10.004" target="_blank" >http://dx.doi.org/10.1016/j.jda.2012.10.004</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.jda.2012.10.004" target="_blank" >10.1016/j.jda.2012.10.004</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On left and right seeds of a string

Popis výsledku v původním jazyce

We consider the problem of finding the repetitive structure of a given string y of length n. A factor u of y is a cover of y, if every letter of y lies within some occurrence of u in y. A string v is a seed of y, if it is a cover of a superstring of y. Aleft seed of y is a prefix of y, that is a cover of a superstring of y. Similarly, a right seed of y is a suffix of y, that is a cover of a superstring of y. An integer array LS is the minimal left-seed (resp. maximal left-seed) array of y, if LS[i] isthe minimal (resp. maximal) length of left seeds of y[0..i]. The minimal right-seed (resp. maximal right-seed) arrayRS of y is defined in a similar fashion. In this article, we present linear-time algorithms for computing all left and right seeds of y, alinear-time algorithm for computing the minimal left-seed array of y, a linear-time solution for computing the maximal left-seed array of y, an O(n log n)-time algorithm for computing the minimal right-seed array of y, and a linear-time

Název v anglickém jazyce

On left and right seeds of a string

Popis výsledku anglicky

We consider the problem of finding the repetitive structure of a given string y of length n. A factor u of y is a cover of y, if every letter of y lies within some occurrence of u in y. A string v is a seed of y, if it is a cover of a superstring of y. Aleft seed of y is a prefix of y, that is a cover of a superstring of y. Similarly, a right seed of y is a suffix of y, that is a cover of a superstring of y. An integer array LS is the minimal left-seed (resp. maximal left-seed) array of y, if LS[i] isthe minimal (resp. maximal) length of left seeds of y[0..i]. The minimal right-seed (resp. maximal right-seed) arrayRS of y is defined in a similar fashion. In this article, we present linear-time algorithms for computing all left and right seeds of y, alinear-time algorithm for computing the minimal left-seed array of y, a linear-time solution for computing the maximal left-seed array of y, an O(n log n)-time algorithm for computing the minimal right-seed array of y, and a linear-time

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2012

Kód důvěrnosti údajů

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

Název periodika

Journal of Discrete Algorithms

ISSN

1570-8667

e-ISSN

—

Svazek periodika

17

Číslo periodika v rámci svazku

December

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

14

Strana od-do

31-44

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—