On the Right-Seed Array of a String
Identifieur interne : 006368 ( Main/Exploration ); précédent : 006367; suivant : 006369On the Right-Seed Array of a String
Auteurs : Michalis Christou [Royaume-Uni] ; Maxime Crochemore [Royaume-Uni, France] ; Ondrej Guth [République tchèque] ; Costas S. Iliopoulos [Royaume-Uni, Australie] ; Solon P. Pissis [Royaume-Uni]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2011.
English descriptors
- KwdEn :
- Algorithm, Array, Cambridge university press, Christou, Constant factor, Corresponding factor, Corresponding factor length, Corresponding factor length range mini maxi, Crochemore, Data structures, Empty string, Linear time, Maximal, Maximal array, Maximal right seed, Minimal array, Minimal right seed, Minimal right seeds, Partitioning, Partitioning algorithm, Queue, Resp, Right seed, Right seeds, Superstring, Time requirements.
- Teeft :
- Algorithm, Array, Cambridge university press, Christou, Constant factor, Corresponding factor, Corresponding factor length, Corresponding factor length range mini maxi, Crochemore, Data structures, Empty string, Linear time, Maximal, Maximal array, Maximal right seed, Minimal array, Minimal right seed, Minimal right seeds, Partitioning, Partitioning algorithm, Queue, Resp, Right seed, Right seeds, Superstring, Time requirements.
Abstract
Abstract: We consider the problem of finding the repetitive structure of a given fixed string y. A factor u of y is a cover of y, if every letter of y falls within some occurrence of u in y. A factor v of y is a seed of y, if it is a cover of a superstring of y. There exist linear-time algorithms for solving the minimal cover problem. The minimal seed problem is of much higher algorithmic difficulty, and no linear-time algorithm is known. In this article, we solve one of its variants – computing the minimal and maximal right-seed array of a given string. A right seed of y is the shortest suffix of y that it is a cover of a superstring of y. An integer array RS is the minimal right-seed (resp. maximal right-seed) array of y, if RS[i] is the minimal (resp. maximal) length of right seeds of $y[0\mathinner{\ldotp\ldotp} i]$ . We present an $\ensuremath{\mathcal{O}}(n\log n)$ time algorithm that computes the minimal right-seed array of a given string, and a linear-time solution to compute the maximal right-seed array by detecting border-free prefixes of the given string.
Url:
DOI: 10.1007/978-3-642-22685-4_43
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001C05
- to stream Istex, to step Curation: 001C05
- to stream Istex, to step Checkpoint: 000787
- to stream Main, to step Merge: 006744
- to stream Main, to step Curation: 006368
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">On the Right-Seed Array of a String</title>
<author><name sortKey="Christou, Michalis" sort="Christou, Michalis" uniqKey="Christou M" first="Michalis" last="Christou">Michalis Christou</name>
</author>
<author><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name>
</author>
<author><name sortKey="Guth, Ondrej" sort="Guth, Ondrej" uniqKey="Guth O" first="Ondrej" last="Guth">Ondrej Guth</name>
</author>
<author><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name>
</author>
<author><name sortKey="Pissis, Solon P" sort="Pissis, Solon P" uniqKey="Pissis S" first="Solon P." last="Pissis">Solon P. Pissis</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:943A61B48CE2151B556A488A6F66336B6CB793CF</idno>
<date when="2011" year="2011">2011</date>
<idno type="doi">10.1007/978-3-642-22685-4_43</idno>
<idno type="url">https://api.istex.fr/document/943A61B48CE2151B556A488A6F66336B6CB793CF/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001C05</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001C05</idno>
<idno type="wicri:Area/Istex/Curation">001C05</idno>
<idno type="wicri:Area/Istex/Checkpoint">000787</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000787</idno>
<idno type="wicri:doubleKey">0302-9743:2011:Christou M:on:the:right</idno>
<idno type="wicri:Area/Main/Merge">006744</idno>
<idno type="wicri:Area/Main/Curation">006368</idno>
<idno type="wicri:Area/Main/Exploration">006368</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">On the Right-Seed Array of a String</title>
<author><name sortKey="Christou, Michalis" sort="Christou, Michalis" uniqKey="Christou M" first="Michalis" last="Christou">Michalis Christou</name>
<affiliation wicri:level="3"><country xml:lang="fr">Royaume-Uni</country>
<wicri:regionArea>Dept. of Informatics, King’s College London, WC2R 2LS, London</wicri:regionArea>
<placeName><settlement type="city">Londres</settlement>
<region type="country">Angleterre</region>
<region type="région" nuts="1">Grand Londres</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Royaume-Uni</country>
</affiliation>
</author>
<author><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name>
<affiliation wicri:level="3"><country xml:lang="fr">Royaume-Uni</country>
<wicri:regionArea>Dept. of Informatics, King’s College London, WC2R 2LS, London</wicri:regionArea>
<placeName><settlement type="city">Londres</settlement>
<region type="country">Angleterre</region>
<region type="région" nuts="1">Grand Londres</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country xml:lang="fr">France</country>
<wicri:regionArea>Université Paris-Est</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Royaume-Uni</country>
</affiliation>
</author>
<author><name sortKey="Guth, Ondrej" sort="Guth, Ondrej" uniqKey="Guth O" first="Ondrej" last="Guth">Ondrej Guth</name>
<affiliation></affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">République tchèque</country>
</affiliation>
</author>
<author><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name>
<affiliation wicri:level="3"><country xml:lang="fr">Royaume-Uni</country>
<wicri:regionArea>Dept. of Informatics, King’s College London, WC2R 2LS, London</wicri:regionArea>
<placeName><settlement type="city">Londres</settlement>
<region type="country">Angleterre</region>
<region type="région" nuts="1">Grand Londres</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country xml:lang="fr">Australie</country>
<wicri:regionArea>Digital Ecosystems & Business Intelligence Institute, Curtin University, GPO Box U1987, 6845, Perth, WA</wicri:regionArea>
<wicri:noRegion>WA</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Royaume-Uni</country>
</affiliation>
</author>
<author><name sortKey="Pissis, Solon P" sort="Pissis, Solon P" uniqKey="Pissis S" first="Solon P." last="Pissis">Solon P. Pissis</name>
<affiliation wicri:level="3"><country xml:lang="fr">Royaume-Uni</country>
<wicri:regionArea>Dept. of Informatics, King’s College London, WC2R 2LS, London</wicri:regionArea>
<placeName><settlement type="city">Londres</settlement>
<region type="country">Angleterre</region>
<region type="région" nuts="1">Grand Londres</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Royaume-Uni</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s">Lecture Notes in Computer Science</title>
<imprint><date>2011</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term>
<term>Array</term>
<term>Cambridge university press</term>
<term>Christou</term>
<term>Constant factor</term>
<term>Corresponding factor</term>
<term>Corresponding factor length</term>
<term>Corresponding factor length range mini maxi</term>
<term>Crochemore</term>
<term>Data structures</term>
<term>Empty string</term>
<term>Linear time</term>
<term>Maximal</term>
<term>Maximal array</term>
<term>Maximal right seed</term>
<term>Minimal array</term>
<term>Minimal right seed</term>
<term>Minimal right seeds</term>
<term>Partitioning</term>
<term>Partitioning algorithm</term>
<term>Queue</term>
<term>Resp</term>
<term>Right seed</term>
<term>Right seeds</term>
<term>Superstring</term>
<term>Time requirements</term>
</keywords>
<keywords scheme="Teeft" xml:lang="en"><term>Algorithm</term>
<term>Array</term>
<term>Cambridge university press</term>
<term>Christou</term>
<term>Constant factor</term>
<term>Corresponding factor</term>
<term>Corresponding factor length</term>
<term>Corresponding factor length range mini maxi</term>
<term>Crochemore</term>
<term>Data structures</term>
<term>Empty string</term>
<term>Linear time</term>
<term>Maximal</term>
<term>Maximal array</term>
<term>Maximal right seed</term>
<term>Minimal array</term>
<term>Minimal right seed</term>
<term>Minimal right seeds</term>
<term>Partitioning</term>
<term>Partitioning algorithm</term>
<term>Queue</term>
<term>Resp</term>
<term>Right seed</term>
<term>Right seeds</term>
<term>Superstring</term>
<term>Time requirements</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: We consider the problem of finding the repetitive structure of a given fixed string y. A factor u of y is a cover of y, if every letter of y falls within some occurrence of u in y. A factor v of y is a seed of y, if it is a cover of a superstring of y. There exist linear-time algorithms for solving the minimal cover problem. The minimal seed problem is of much higher algorithmic difficulty, and no linear-time algorithm is known. In this article, we solve one of its variants – computing the minimal and maximal right-seed array of a given string. A right seed of y is the shortest suffix of y that it is a cover of a superstring of y. An integer array RS is the minimal right-seed (resp. maximal right-seed) array of y, if RS[i] is the minimal (resp. maximal) length of right seeds of $y[0\mathinner{\ldotp\ldotp} i]$ . We present an $\ensuremath{\mathcal{O}}(n\log n)$ time algorithm that computes the minimal right-seed array of a given string, and a linear-time solution to compute the maximal right-seed array by detecting border-free prefixes of the given string.</div>
</front>
</TEI>
<affiliations><list><country><li>Australie</li>
<li>France</li>
<li>Royaume-Uni</li>
<li>République tchèque</li>
</country>
<region><li>Angleterre</li>
<li>Grand Londres</li>
</region>
<settlement><li>Londres</li>
</settlement>
</list>
<tree><country name="Royaume-Uni"><region name="Angleterre"><name sortKey="Christou, Michalis" sort="Christou, Michalis" uniqKey="Christou M" first="Michalis" last="Christou">Michalis Christou</name>
</region>
<name sortKey="Christou, Michalis" sort="Christou, Michalis" uniqKey="Christou M" first="Michalis" last="Christou">Michalis Christou</name>
<name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name>
<name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name>
<name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name>
<name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name>
<name sortKey="Pissis, Solon P" sort="Pissis, Solon P" uniqKey="Pissis S" first="Solon P." last="Pissis">Solon P. Pissis</name>
<name sortKey="Pissis, Solon P" sort="Pissis, Solon P" uniqKey="Pissis S" first="Solon P." last="Pissis">Solon P. Pissis</name>
</country>
<country name="France"><noRegion><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name>
</noRegion>
</country>
<country name="République tchèque"><noRegion><name sortKey="Guth, Ondrej" sort="Guth, Ondrej" uniqKey="Guth O" first="Ondrej" last="Guth">Ondrej Guth</name>
</noRegion>
</country>
<country name="Australie"><noRegion><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name>
</noRegion>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006368 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 006368 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Asie |area= AustralieFrV1 |flux= Main |étape= Exploration |type= RBID |clé= ISTEX:943A61B48CE2151B556A488A6F66336B6CB793CF |texte= On the Right-Seed Array of a String }}
This area was generated with Dilib version V0.6.33. |