Efficient Seeds Computation Revisited
Identifieur interne : 001422 ( Istex/Corpus ); précédent : 001421; suivant : 001423Efficient Seeds Computation Revisited
Auteurs : Michalis Christou ; Maxime Crochemore ; Costas S. Iliopoulos ; Marcin Kubica ; Solon P. Pissis ; Jakub Radoszewski ; Wojciech Rytter ; Bartosz Szreder ; Tomasz WaleSource :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2011.
English descriptors
- KwdEn :
- Algorithm, Alternative algorithm, Array, Auxiliary array, Border array, Border seed, Cambridge university press, Canonical form, Chain maxgap problem, Chain maxgap problems, Computer science, Computeshortestseed algorithm, Corresponding seed, Data structure, Input string, Leaf list, Linear time, Linear time algorithm, Linear time algorithms, Longest array, Lseedm, Maxgap, Maxgap problem, Maxgaps, National science centre, Node, Period array, Pref, Right seed, Seed array, Seeds computation, Shortest, Shortest seed, Shortest seeds, Simple characterization, Stores elements, Time algorithm, Time complexity, Total size, Total time, Whole string.
- Teeft :
- Algorithm, Alternative algorithm, Array, Auxiliary array, Border array, Border seed, Cambridge university press, Canonical form, Chain maxgap problem, Chain maxgap problems, Computer science, Computeshortestseed algorithm, Corresponding seed, Data structure, Input string, Leaf list, Linear time, Linear time algorithm, Linear time algorithms, Longest array, Lseedm, Maxgap, Maxgap problem, Maxgaps, National science centre, Node, Period array, Pref, Right seed, Seed array, Seeds computation, Shortest, Shortest seed, Shortest seeds, Simple characterization, Stores elements, Time algorithm, Time complexity, Total size, Total time, Whole string.
Abstract
Abstract: The notion of the cover is a generalization of a period of a string, and there are linear time algorithms for finding the shortest cover. The seed is a more complicated generalization of periodicity, it is a cover of a superstring of a given string, and the shortest seed problem is of much higher algorithmic difficulty. The problem is not well understood, no linear time algorithm is known. In the paper we give linear time algorithms for some of its versions — computing shortest left-seed array, longest left-seed array and checking for seeds of a given length. The algorithm for the last problem is used to compute the seed array of a string (i.e., the shortest seeds for all the prefixes of the string) in O(n 2) time. We describe also a simpler alternative algorithm computing efficiently the shortest seeds. As a by-product we obtain an O(nlog(n/m)) time algorithm checking if the shortest seed has length at least m and finding the corresponding seed. We also correct some important details missing in the previously known shortest-seed algorithm (Iliopoulos et al., 1996).
Url:
DOI: 10.1007/978-3-642-21458-5_30
Links to Exploration step
ISTEX:6C0A668C2EFEFF27F9DD326D65984E9A158771B3Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Efficient Seeds Computation Revisited</title><author><name sortKey="Christou, Michalis" sort="Christou, Michalis" uniqKey="Christou M" first="Michalis" last="Christou">Michalis Christou</name><affiliation><mods:affiliation>Dept. of Informatics, King’s College London, WC2R 2LS, London, UK</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: michalis.christou@dcs.kcl.ac.uk</mods:affiliation></affiliation></author><author><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name><affiliation><mods:affiliation>Dept. of Informatics, King’s College London, WC2R 2LS, London, UK</mods:affiliation></affiliation><affiliation><mods:affiliation>Université Paris-Est, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: maxime.crochemore@dcs.kcl.ac.uk</mods:affiliation></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><mods:affiliation>Dept. of Informatics, King’s College London, WC2R 2LS, London, UK</mods:affiliation></affiliation><affiliation><mods:affiliation>Digital Ecosystems & Business Intelligence Institute, Curtin University of Technology, 6845, Perth, WA, Australia</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: csi@dcs.kcl.ac.uk</mods:affiliation></affiliation></author><author><name sortKey="Kubica, Marcin" sort="Kubica, Marcin" uniqKey="Kubica M" first="Marcin" last="Kubica">Marcin Kubica</name><affiliation><mods:affiliation>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: kubica@mimuw.edu.pl</mods:affiliation></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><mods:affiliation>Dept. of Informatics, King’s College London, WC2R 2LS, London, UK</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: solon.pissis@dcs.kcl.ac.uk</mods:affiliation></affiliation></author><author><name sortKey="Radoszewski, Jakub" sort="Radoszewski, Jakub" uniqKey="Radoszewski J" first="Jakub" last="Radoszewski">Jakub Radoszewski</name><affiliation><mods:affiliation>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: jrad@mimuw.edu.pl</mods:affiliation></affiliation></author><author><name sortKey="Rytter, Wojciech" sort="Rytter, Wojciech" uniqKey="Rytter W" first="Wojciech" last="Rytter">Wojciech Rytter</name><affiliation><mods:affiliation>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</mods:affiliation></affiliation><affiliation><mods:affiliation>Dept. of Math. and Informatics, Copernicus University, Toruń, Poland</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: rytter@mimuw.edu.pl</mods:affiliation></affiliation></author><author><name sortKey="Szreder, Bartosz" sort="Szreder, Bartosz" uniqKey="Szreder B" first="Bartosz" last="Szreder">Bartosz Szreder</name><affiliation><mods:affiliation>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: szreder@mimuw.edu.pl</mods:affiliation></affiliation></author><author><name sortKey="Wale, Tomasz" sort="Wale, Tomasz" uniqKey="Wale T" first="Tomasz" last="Wale">Tomasz Wale</name><affiliation><mods:affiliation>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: walen@mimuw.edu.pl</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:6C0A668C2EFEFF27F9DD326D65984E9A158771B3</idno><date when="2011" year="2011">2011</date><idno type="doi">10.1007/978-3-642-21458-5_30</idno><idno type="url">https://api.istex.fr/document/6C0A668C2EFEFF27F9DD326D65984E9A158771B3/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001422</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001422</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Efficient Seeds Computation Revisited</title><author><name sortKey="Christou, Michalis" sort="Christou, Michalis" uniqKey="Christou M" first="Michalis" last="Christou">Michalis Christou</name><affiliation><mods:affiliation>Dept. of Informatics, King’s College London, WC2R 2LS, London, UK</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: michalis.christou@dcs.kcl.ac.uk</mods:affiliation></affiliation></author><author><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name><affiliation><mods:affiliation>Dept. of Informatics, King’s College London, WC2R 2LS, London, UK</mods:affiliation></affiliation><affiliation><mods:affiliation>Université Paris-Est, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: maxime.crochemore@dcs.kcl.ac.uk</mods:affiliation></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><mods:affiliation>Dept. of Informatics, King’s College London, WC2R 2LS, London, UK</mods:affiliation></affiliation><affiliation><mods:affiliation>Digital Ecosystems & Business Intelligence Institute, Curtin University of Technology, 6845, Perth, WA, Australia</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: csi@dcs.kcl.ac.uk</mods:affiliation></affiliation></author><author><name sortKey="Kubica, Marcin" sort="Kubica, Marcin" uniqKey="Kubica M" first="Marcin" last="Kubica">Marcin Kubica</name><affiliation><mods:affiliation>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: kubica@mimuw.edu.pl</mods:affiliation></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><mods:affiliation>Dept. of Informatics, King’s College London, WC2R 2LS, London, UK</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: solon.pissis@dcs.kcl.ac.uk</mods:affiliation></affiliation></author><author><name sortKey="Radoszewski, Jakub" sort="Radoszewski, Jakub" uniqKey="Radoszewski J" first="Jakub" last="Radoszewski">Jakub Radoszewski</name><affiliation><mods:affiliation>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: jrad@mimuw.edu.pl</mods:affiliation></affiliation></author><author><name sortKey="Rytter, Wojciech" sort="Rytter, Wojciech" uniqKey="Rytter W" first="Wojciech" last="Rytter">Wojciech Rytter</name><affiliation><mods:affiliation>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</mods:affiliation></affiliation><affiliation><mods:affiliation>Dept. of Math. and Informatics, Copernicus University, Toruń, Poland</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: rytter@mimuw.edu.pl</mods:affiliation></affiliation></author><author><name sortKey="Szreder, Bartosz" sort="Szreder, Bartosz" uniqKey="Szreder B" first="Bartosz" last="Szreder">Bartosz Szreder</name><affiliation><mods:affiliation>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: szreder@mimuw.edu.pl</mods:affiliation></affiliation></author><author><name sortKey="Wale, Tomasz" sort="Wale, Tomasz" uniqKey="Wale T" first="Tomasz" last="Wale">Tomasz Wale</name><affiliation><mods:affiliation>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: walen@mimuw.edu.pl</mods:affiliation></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>Alternative algorithm</term><term>Array</term><term>Auxiliary array</term><term>Border array</term><term>Border seed</term><term>Cambridge university press</term><term>Canonical form</term><term>Chain maxgap problem</term><term>Chain maxgap problems</term><term>Computer science</term><term>Computeshortestseed algorithm</term><term>Corresponding seed</term><term>Data structure</term><term>Input string</term><term>Leaf list</term><term>Linear time</term><term>Linear time algorithm</term><term>Linear time algorithms</term><term>Longest array</term><term>Lseedm</term><term>Maxgap</term><term>Maxgap problem</term><term>Maxgaps</term><term>National science centre</term><term>Node</term><term>Period array</term><term>Pref</term><term>Right seed</term><term>Seed array</term><term>Seeds computation</term><term>Shortest</term><term>Shortest seed</term><term>Shortest seeds</term><term>Simple characterization</term><term>Stores elements</term><term>Time algorithm</term><term>Time complexity</term><term>Total size</term><term>Total time</term><term>Whole string</term></keywords><keywords scheme="Teeft" xml:lang="en"><term>Algorithm</term><term>Alternative algorithm</term><term>Array</term><term>Auxiliary array</term><term>Border array</term><term>Border seed</term><term>Cambridge university press</term><term>Canonical form</term><term>Chain maxgap problem</term><term>Chain maxgap problems</term><term>Computer science</term><term>Computeshortestseed algorithm</term><term>Corresponding seed</term><term>Data structure</term><term>Input string</term><term>Leaf list</term><term>Linear time</term><term>Linear time algorithm</term><term>Linear time algorithms</term><term>Longest array</term><term>Lseedm</term><term>Maxgap</term><term>Maxgap problem</term><term>Maxgaps</term><term>National science centre</term><term>Node</term><term>Period array</term><term>Pref</term><term>Right seed</term><term>Seed array</term><term>Seeds computation</term><term>Shortest</term><term>Shortest seed</term><term>Shortest seeds</term><term>Simple characterization</term><term>Stores elements</term><term>Time algorithm</term><term>Time complexity</term><term>Total size</term><term>Total time</term><term>Whole string</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: The notion of the cover is a generalization of a period of a string, and there are linear time algorithms for finding the shortest cover. The seed is a more complicated generalization of periodicity, it is a cover of a superstring of a given string, and the shortest seed problem is of much higher algorithmic difficulty. The problem is not well understood, no linear time algorithm is known. In the paper we give linear time algorithms for some of its versions — computing shortest left-seed array, longest left-seed array and checking for seeds of a given length. The algorithm for the last problem is used to compute the seed array of a string (i.e., the shortest seeds for all the prefixes of the string) in O(n 2) time. We describe also a simpler alternative algorithm computing efficiently the shortest seeds. As a by-product we obtain an O(nlog(n/m)) time algorithm checking if the shortest seed has length at least m and finding the corresponding seed. We also correct some important details missing in the previously known shortest-seed algorithm (Iliopoulos et al., 1996).</div></front></TEI><istex><corpusName>springer</corpusName><keywords><teeft><json:string>algorithm</json:string><json:string>maxgap</json:string><json:string>maxgaps</json:string><json:string>shortest seed</json:string><json:string>pref</json:string><json:string>border seed</json:string><json:string>node</json:string><json:string>seeds computation</json:string><json:string>seed array</json:string><json:string>period array</json:string><json:string>time algorithm</json:string><json:string>linear time</json:string><json:string>lseedm</json:string><json:string>shortest</json:string><json:string>maxgap problem</json:string><json:string>longest array</json:string><json:string>shortest seeds</json:string><json:string>border array</json:string><json:string>alternative algorithm</json:string><json:string>cambridge university press</json:string><json:string>total time</json:string><json:string>chain maxgap problem</json:string><json:string>linear time algorithms</json:string><json:string>whole string</json:string><json:string>computeshortestseed algorithm</json:string><json:string>total size</json:string><json:string>array</json:string><json:string>computer science</json:string><json:string>input string</json:string><json:string>simple characterization</json:string><json:string>canonical form</json:string><json:string>data structure</json:string><json:string>right seed</json:string><json:string>leaf list</json:string><json:string>stores elements</json:string><json:string>corresponding seed</json:string><json:string>linear time algorithm</json:string><json:string>auxiliary array</json:string><json:string>chain maxgap problems</json:string><json:string>national science centre</json:string><json:string>time complexity</json:string></teeft></keywords><author><json:item><name>Michalis Christou</name><affiliations><json:string>Dept. of Informatics, King’s College London, WC2R 2LS, London, UK</json:string><json:string>E-mail: michalis.christou@dcs.kcl.ac.uk</json:string></affiliations></json:item><json:item><name>Maxime Crochemore</name><affiliations><json:string>Dept. of Informatics, King’s College London, WC2R 2LS, London, UK</json:string><json:string>Université Paris-Est, France</json:string><json:string>E-mail: maxime.crochemore@dcs.kcl.ac.uk</json:string></affiliations></json:item><json:item><name>Costas S. Iliopoulos</name><affiliations><json:string>Dept. of Informatics, King’s College London, WC2R 2LS, London, UK</json:string><json:string>Digital Ecosystems & Business Intelligence Institute, Curtin University of Technology, 6845, Perth, WA, Australia</json:string><json:string>E-mail: csi@dcs.kcl.ac.uk</json:string></affiliations></json:item><json:item><name>Marcin Kubica</name><affiliations><json:string>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</json:string><json:string>E-mail: kubica@mimuw.edu.pl</json:string></affiliations></json:item><json:item><name>Solon P. Pissis</name><affiliations><json:string>Dept. of Informatics, King’s College London, WC2R 2LS, London, UK</json:string><json:string>E-mail: solon.pissis@dcs.kcl.ac.uk</json:string></affiliations></json:item><json:item><name>Jakub Radoszewski</name><affiliations><json:string>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</json:string><json:string>E-mail: jrad@mimuw.edu.pl</json:string></affiliations></json:item><json:item><name>Wojciech Rytter</name><affiliations><json:string>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</json:string><json:string>Dept. of Math. and Informatics, Copernicus University, Toruń, Poland</json:string><json:string>E-mail: rytter@mimuw.edu.pl</json:string></affiliations></json:item><json:item><name>Bartosz Szreder</name><affiliations><json:string>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</json:string><json:string>E-mail: szreder@mimuw.edu.pl</json:string></affiliations></json:item><json:item><name>Tomasz Waleń</name><affiliations><json:string>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</json:string><json:string>E-mail: walen@mimuw.edu.pl</json:string></affiliations></json:item></author><arkIstex>ark:/67375/1BB-ML8861L6-1</arkIstex><language><json:string>eng</json:string></language><originalGenre><json:string>OriginalPaper</json:string></originalGenre><abstract>Abstract: The notion of the cover is a generalization of a period of a string, and there are linear time algorithms for finding the shortest cover. The seed is a more complicated generalization of periodicity, it is a cover of a superstring of a given string, and the shortest seed problem is of much higher algorithmic difficulty. The problem is not well understood, no linear time algorithm is known. In the paper we give linear time algorithms for some of its versions — computing shortest left-seed array, longest left-seed array and checking for seeds of a given length. The algorithm for the last problem is used to compute the seed array of a string (i.e., the shortest seeds for all the prefixes of the string) in O(n 2) time. We describe also a simpler alternative algorithm computing efficiently the shortest seeds. As a by-product we obtain an O(nlog(n/m)) time algorithm checking if the shortest seed has length at least m and finding the corresponding seed. We also correct some important details missing in the previously known shortest-seed algorithm (Iliopoulos et al., 1996).</abstract><qualityIndicators><score>9.184</score><pdfWordCount>5694</pdfWordCount><pdfCharCount>26221</pdfCharCount><pdfVersion>1.6</pdfVersion><pdfPageCount>14</pdfPageCount><pdfPageSize>429.442 x 659.895 pts</pdfPageSize><refBibsNative>false</refBibsNative><abstractWordCount>182</abstractWordCount><abstractCharCount>1092</abstractCharCount><keywordCount>0</keywordCount></qualityIndicators><title>Efficient Seeds Computation Revisited</title><chapterId><json:string>30</json:string><json:string>Chap30</json:string></chapterId><genre><json:string>conference</json:string></genre><serie><title>Lecture Notes in Computer Science</title><language><json:string>unknown</json:string></language><copyrightDate>2011</copyrightDate><issn><json:string>0302-9743</json:string></issn><eissn><json:string>1611-3349</json:string></eissn><editor><json:item><name>David Hutchison</name><affiliations><json:string>Lancaster University, Lancaster, UK</json:string></affiliations></json:item><json:item><name>Takeo Kanade</name><affiliations><json:string>Carnegie Mellon University, Pittsburgh, PA, USA</json:string></affiliations></json:item><json:item><name>Josef Kittler</name><affiliations><json:string>University of Surrey, Guildford, UK</json:string></affiliations></json:item><json:item><name>Jon M. Kleinberg</name><affiliations><json:string>Cornell University, Ithaca, NY, USA</json:string></affiliations></json:item><json:item><name>Friedemann Mattern</name><affiliations><json:string>ETH Zurich, Zurich, Switzerland</json:string></affiliations></json:item><json:item><name>John C. Mitchell</name><affiliations><json:string>Stanford University, Stanford, CA, USA</json:string></affiliations></json:item><json:item><name>Moni Naor</name><affiliations><json:string>Weizmann Institute of Science, Rehovot, Israel</json:string></affiliations></json:item><json:item><name>Oscar Nierstrasz</name><affiliations><json:string>University of Bern, Bern, Switzerland</json:string></affiliations></json:item><json:item><name>C. Pandu Rangan</name><affiliations><json:string>Indian Institute of Technology, Madras, India</json:string></affiliations></json:item><json:item><name>Bernhard Steffen</name><affiliations><json:string>University of Dortmund, Dortmund, Germany</json:string></affiliations></json:item><json:item><name>Madhu Sudan</name><affiliations><json:string>Massachusetts Institute of Technology, MA, USA</json:string></affiliations></json:item><json:item><name>Demetri Terzopoulos</name><affiliations><json:string>University of California, Los Angeles, CA, USA</json:string></affiliations></json:item><json:item><name>Doug Tygar</name><affiliations><json:string>University of California, Berkeley, CA, USA</json:string></affiliations></json:item><json:item><name>Moshe Y. Vardi</name><affiliations><json:string>Rice University, Houston, TX, USA</json:string></affiliations></json:item><json:item><name>Gerhard Weikum</name><affiliations><json:string>Max-Planck Institute of Computer Science, Saarbrücken, Germany</json:string></affiliations></json:item></editor></serie><host><title>Combinatorial Pattern Matching</title><language><json:string>unknown</json:string></language><copyrightDate>2011</copyrightDate><doi><json:string>10.1007/978-3-642-21458-5</json:string></doi><issn><json:string>0302-9743</json:string></issn><eissn><json:string>1611-3349</json:string></eissn><eisbn><json:string>978-3-642-21458-5</json:string></eisbn><bookId><json:string>978-3-642-21458-5</json:string></bookId><isbn><json:string>978-3-642-21457-8</json:string></isbn><volume>6661</volume><pages><first>350</first><last>363</last></pages><genre><json:string>book-series</json:string></genre><editor><json:item><name>Raffaele Giancarlo</name><affiliations><json:string>Department of Mathematics, Università degli Studi di Palermo, Via Archirafi 34, 90123, Palermo, Italy</json:string><json:string>E-mail: raffaele@mfn.unipmn.it</json:string></affiliations></json:item><json:item><name>Giovanni Manzini</name><affiliations><json:string>Department of Computer Science, University of ’Piemonte Orientale’, Viale T. Michel 11, 15121, Alessandria, Italy</json:string><json:string>E-mail: manzini@mfn.unipmn.it</json:string></affiliations></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Algorithm Analysis and Problem Complexity</value></json:item><json:item><value>Data Structures</value></json:item><json:item><value>Data Mining and Knowledge Discovery</value></json:item><json:item><value>Pattern Recognition</value></json:item><json:item><value>Computational Biology/Bioinformatics</value></json:item><json:item><value>Bioinformatics</value></json:item></subject></host><namedEntities><unitex><date><json:string>2011</json:string></date><geogName></geogName><orgName><json:string>Business Intelligence Institute, Curtin University of Technology, Perth WA</json:string><json:string>National Science Centre</json:string><json:string>Copernicus University</json:string></orgName><orgName_funder></orgName_funder><orgName_provider></orgName_provider><persName><json:string>Jakub Radoszewski</json:string><json:string>G. Manzini</json:string><json:string>S. Iliopoulos</json:string><json:string>Wojciech Rytter</json:string><json:string>Please</json:string><json:string>Solon P. Pissis</json:string><json:string>R. Giancarlo</json:string><json:string>Marcin Kubica</json:string></persName><placeName><json:string>Australia</json:string><json:string>Heidelberg</json:string><json:string>Poland</json:string><json:string>Warsaw</json:string></placeName><ref_url></ref_url><ref_bibl><json:string>Iliopoulos et al., 1996</json:string><json:string>[7,10]</json:string><json:string>[12]</json:string><json:string>[1,4]</json:string><json:string>M. Christou et al.</json:string><json:string>[6]</json:string><json:string>[11]</json:string><json:string>[1,4,6,8]</json:string><json:string>[6,8]</json:string><json:string>[9,15]</json:string><json:string>[3]</json:string><json:string>[13,14]</json:string><json:string>[5]</json:string><json:string>[2]</json:string></ref_bibl><bibl></bibl></unitex></namedEntities><ark><json:string>ark:/67375/1BB-ML8861L6-1</json:string></ark><categories><inist><json:string>1 - sciences appliquees, technologies et medecines</json:string><json:string>2 - sciences exactes et technologie</json:string><json:string>3 - sciences et techniques communes</json:string><json:string>4 - mathematiques</json:string></inist></categories><publicationDate>2011</publicationDate><copyrightDate>2011</copyrightDate><doi><json:string>10.1007/978-3-642-21458-5_30</json:string></doi><id>6C0A668C2EFEFF27F9DD326D65984E9A158771B3</id><score>1</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/6C0A668C2EFEFF27F9DD326D65984E9A158771B3/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/6C0A668C2EFEFF27F9DD326D65984E9A158771B3/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/6C0A668C2EFEFF27F9DD326D65984E9A158771B3/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Efficient Seeds Computation Revisited</title><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt></titleStmt><publicationStmt><authority>ISTEX</authority><publisher scheme="https://publisher-list.data.istex.fr">Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><availability><licence><p>Springer Berlin Heidelberg, 2011</p></licence><p scheme="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-3XSW68JL-F">springer</p></availability><date>2011</date></publicationStmt><notesStmt><note type="conference" scheme="https://content-type.data.istex.fr/ark:/67375/XTP-BFHXPBJJ-3">conference</note><note type="book-series" scheme="https://publication-type.data.istex.fr/ark:/67375/JMC-0G6R5W5T-Z">book-series</note></notesStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">Efficient Seeds Computation Revisited</title><author xml:id="author-0000"><persName><forename type="first">Michalis</forename><surname>Christou</surname></persName><email>michalis.christou@dcs.kcl.ac.uk</email><affiliation>Dept. of Informatics, King’s College London, WC2R 2LS, London, UK</affiliation></author><author xml:id="author-0001"><persName><forename type="first">Maxime</forename><surname>Crochemore</surname></persName><email>maxime.crochemore@dcs.kcl.ac.uk</email><affiliation>Dept. of Informatics, King’s College London, WC2R 2LS, London, UK</affiliation><affiliation>Université Paris-Est, France</affiliation></author><author xml:id="author-0002"><persName><forename type="first">Costas</forename><surname>Iliopoulos</surname></persName><email>csi@dcs.kcl.ac.uk</email><affiliation>Dept. of Informatics, King’s College London, WC2R 2LS, London, UK</affiliation><affiliation>Digital Ecosystems & Business Intelligence Institute, Curtin University of Technology, 6845, Perth, WA, Australia</affiliation></author><author xml:id="author-0003"><persName><forename type="first">Marcin</forename><surname>Kubica</surname></persName><email>kubica@mimuw.edu.pl</email><affiliation>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</affiliation></author><author xml:id="author-0004"><persName><forename type="first">Solon</forename><surname>Pissis</surname></persName><email>solon.pissis@dcs.kcl.ac.uk</email><affiliation>Dept. of Informatics, King’s College London, WC2R 2LS, London, UK</affiliation></author><author xml:id="author-0005"><persName><forename type="first">Jakub</forename><surname>Radoszewski</surname></persName><email>jrad@mimuw.edu.pl</email><affiliation>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</affiliation></author><author xml:id="author-0006"><persName><forename type="first">Wojciech</forename><surname>Rytter</surname></persName><email>rytter@mimuw.edu.pl</email><affiliation>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</affiliation><affiliation>Dept. of Math. and Informatics, Copernicus University, Toruń, Poland</affiliation></author><author xml:id="author-0007"><persName><forename type="first">Bartosz</forename><surname>Szreder</surname></persName><email>szreder@mimuw.edu.pl</email><affiliation>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</affiliation></author><author xml:id="author-0008"><persName><forename type="first">Tomasz</forename><surname>Waleń</surname></persName><email>walen@mimuw.edu.pl</email><affiliation>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</affiliation></author><idno type="istex">6C0A668C2EFEFF27F9DD326D65984E9A158771B3</idno><idno type="ark">ark:/67375/1BB-ML8861L6-1</idno><idno type="DOI">10.1007/978-3-642-21458-5_30</idno><idno type="ChapterID">30</idno><idno type="ChapterID">Chap30</idno></analytic><monogr><title level="m">Combinatorial Pattern Matching</title><title level="m" type="sub">22nd Annual Symposium, CPM 2011, Palermo, Italy, June 27-29, 2011. Proceedings</title><idno type="DOI">10.1007/978-3-642-21458-5</idno><idno type="pISBN">978-3-642-21457-8</idno><idno type="eISBN">978-3-642-21458-5</idno><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="book-title-id">270808</idno><idno type="book-id">978-3-642-21458-5</idno><idno type="book-chapter-count">39</idno><idno type="book-volume-number">6661</idno><idno type="book-sequence-number">6661</idno><idno type="PartChapterCount">36</idno><editor xml:id="book-author-0000"><persName><forename type="first">Raffaele</forename><surname>Giancarlo</surname></persName><email>raffaele@mfn.unipmn.it</email><affiliation>Department of Mathematics, Università degli Studi di Palermo, Via Archirafi 34, 90123, Palermo, Italy</affiliation></editor><editor xml:id="book-author-0001"><persName><forename type="first">Giovanni</forename><surname>Manzini</surname></persName><email>manzini@mfn.unipmn.it</email><affiliation>Department of Computer Science, University of ’Piemonte Orientale’, Viale T. Michel 11, 15121, Alessandria, Italy</affiliation></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="2011"></date><biblScope unit="volume">6661</biblScope><biblScope unit="page" from="350">350</biblScope><biblScope unit="page" to="363">363</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><editor xml:id="serie-author-0000"><persName><forename type="first">David</forename><surname>Hutchison</surname></persName><affiliation>Lancaster University, Lancaster, UK</affiliation></editor><editor xml:id="serie-author-0001"><persName><forename type="first">Takeo</forename><surname>Kanade</surname></persName><affiliation>Carnegie Mellon University, Pittsburgh, PA, USA</affiliation></editor><editor xml:id="serie-author-0002"><persName><forename type="first">Josef</forename><surname>Kittler</surname></persName><affiliation>University of Surrey, Guildford, UK</affiliation></editor><editor xml:id="serie-author-0003"><persName><forename type="first">Jon</forename><forename type="first">M.</forename><surname>Kleinberg</surname></persName><affiliation>Cornell University, Ithaca, NY, USA</affiliation></editor><editor xml:id="serie-author-0004"><persName><forename type="first">Friedemann</forename><surname>Mattern</surname></persName><affiliation>ETH Zurich, Zurich, Switzerland</affiliation></editor><editor xml:id="serie-author-0005"><persName><forename type="first">John</forename><forename type="first">C.</forename><surname>Mitchell</surname></persName><affiliation>Stanford University, Stanford, CA, USA</affiliation></editor><editor xml:id="serie-author-0006"><persName><forename type="first">Moni</forename><surname>Naor</surname></persName><affiliation>Weizmann Institute of Science, Rehovot, Israel</affiliation></editor><editor xml:id="serie-author-0007"><persName><forename type="first">Oscar</forename><surname>Nierstrasz</surname></persName><affiliation>University of Bern, Bern, Switzerland</affiliation></editor><editor xml:id="serie-author-0008"><persName><forename type="first">C.</forename><surname>Pandu Rangan</surname></persName><affiliation>Indian Institute of Technology, Madras, India</affiliation></editor><editor xml:id="serie-author-0009"><persName><forename type="first">Bernhard</forename><surname>Steffen</surname></persName><affiliation>University of Dortmund, Dortmund, Germany</affiliation></editor><editor xml:id="serie-author-0010"><persName><forename type="first">Madhu</forename><surname>Sudan</surname></persName><affiliation>Massachusetts Institute of Technology, MA, USA</affiliation></editor><editor xml:id="serie-author-0011"><persName><forename type="first">Demetri</forename><surname>Terzopoulos</surname></persName><affiliation>University of California, Los Angeles, CA, USA</affiliation></editor><editor xml:id="serie-author-0012"><persName><forename type="first">Doug</forename><surname>Tygar</surname></persName><affiliation>University of California, Berkeley, CA, USA</affiliation></editor><editor xml:id="serie-author-0013"><persName><forename type="first">Moshe</forename><forename type="first">Y.</forename><surname>Vardi</surname></persName><affiliation>Rice University, Houston, TX, USA</affiliation></editor><editor xml:id="serie-author-0014"><persName><forename type="first">Gerhard</forename><surname>Weikum</surname></persName><affiliation>Max-Planck Institute of Computer Science, Saarbrücken, Germany</affiliation></editor><biblScope><date>2011</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="series-id">558</idno></series></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>2011</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: The notion of the cover is a generalization of a period of a string, and there are linear time algorithms for finding the shortest cover. The seed is a more complicated generalization of periodicity, it is a cover of a superstring of a given string, and the shortest seed problem is of much higher algorithmic difficulty. The problem is not well understood, no linear time algorithm is known. In the paper we give linear time algorithms for some of its versions — computing shortest left-seed array, longest left-seed array and checking for seeds of a given length. The algorithm for the last problem is used to compute the seed array of a string (i.e., the shortest seeds for all the prefixes of the string) in O(n 2) time. We describe also a simpler alternative algorithm computing efficiently the shortest seeds. As a by-product we obtain an O(nlog(n/m)) time algorithm checking if the shortest seed has length at least m and finding the corresponding seed. We also correct some important details missing in the previously known shortest-seed algorithm (Iliopoulos et al., 1996).</p></abstract><textClass><keywords scheme="Book-Subject-Collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass><keywords scheme="Book-Subject-Group"><list><label>I</label><label>I16021</label><label>I15017</label><label>I18030</label><label>I2203X</label><label>I23050</label><label>L15001</label><item><term>Computer Science</term></item><item><term>Algorithm Analysis and Problem Complexity</term></item><item><term>Data Structures</term></item><item><term>Data Mining and Knowledge Discovery</term></item><item><term>Pattern Recognition</term></item><item><term>Computational Biology/Bioinformatics</term></item><item><term>Bioinformatics</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2011">Published</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2017-10-3">References added</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/6C0A668C2EFEFF27F9DD326D65984E9A158771B3/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Springer, Publisher found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo SeriesType="Series" TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor AffiliationIDS="Aff1"><EditorName DisplayOrder="Western"><GivenName>David</GivenName><FamilyName>Hutchison</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff2"><EditorName DisplayOrder="Western"><GivenName>Takeo</GivenName><FamilyName>Kanade</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff3"><EditorName DisplayOrder="Western"><GivenName>Josef</GivenName><FamilyName>Kittler</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff4"><EditorName DisplayOrder="Western"><GivenName>Jon</GivenName><GivenName>M.</GivenName><FamilyName>Kleinberg</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff5"><EditorName DisplayOrder="Western"><GivenName>Friedemann</GivenName><FamilyName>Mattern</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff6"><EditorName DisplayOrder="Western"><GivenName>John</GivenName><GivenName>C.</GivenName><FamilyName>Mitchell</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff7"><EditorName DisplayOrder="Western"><GivenName>Moni</GivenName><FamilyName>Naor</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff8"><EditorName DisplayOrder="Western"><GivenName>Oscar</GivenName><FamilyName>Nierstrasz</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff9"><EditorName DisplayOrder="Western"><GivenName>C.</GivenName><FamilyName>Pandu Rangan</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff10"><EditorName DisplayOrder="Western"><GivenName>Bernhard</GivenName><FamilyName>Steffen</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff11"><EditorName DisplayOrder="Western"><GivenName>Madhu</GivenName><FamilyName>Sudan</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff12"><EditorName DisplayOrder="Western"><GivenName>Demetri</GivenName><FamilyName>Terzopoulos</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff13"><EditorName DisplayOrder="Western"><GivenName>Doug</GivenName><FamilyName>Tygar</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff14"><EditorName DisplayOrder="Western"><GivenName>Moshe</GivenName><GivenName>Y.</GivenName><FamilyName>Vardi</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff15"><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Weikum</FamilyName></EditorName></Editor><Affiliation ID="Aff1"><OrgName>Lancaster University</OrgName><OrgAddress><City>Lancaster</City><Country>UK</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgName>Carnegie Mellon University</OrgName><OrgAddress><City>Pittsburgh</City><State>PA</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff3"><OrgName>University of Surrey</OrgName><OrgAddress><City>Guildford</City><Country>UK</Country></OrgAddress></Affiliation><Affiliation ID="Aff4"><OrgName>Cornell University</OrgName><OrgAddress><City>Ithaca</City><State>NY</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff5"><OrgName>ETH Zurich</OrgName><OrgAddress><City>Zurich</City><Country>Switzerland</Country></OrgAddress></Affiliation><Affiliation ID="Aff6"><OrgName>Stanford University</OrgName><OrgAddress><City>Stanford</City><State>CA</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff7"><OrgName>Weizmann Institute of Science</OrgName><OrgAddress><City>Rehovot</City><Country>Israel</Country></OrgAddress></Affiliation><Affiliation ID="Aff8"><OrgName>University of Bern</OrgName><OrgAddress><City>Bern</City><Country>Switzerland</Country></OrgAddress></Affiliation><Affiliation ID="Aff9"><OrgName>Indian Institute of Technology</OrgName><OrgAddress><City>Madras</City><Country>India</Country></OrgAddress></Affiliation><Affiliation ID="Aff10"><OrgName>University of Dortmund</OrgName><OrgAddress><City>Dortmund</City><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff11"><OrgName>Massachusetts Institute of Technology</OrgName><OrgAddress><State>MA</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff12"><OrgName>University of California</OrgName><OrgAddress><City>Los Angeles</City><State>CA</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff13"><OrgName>University of California</OrgName><OrgAddress><City>Berkeley</City><State>CA</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff14"><OrgName>Rice University</OrgName><OrgAddress><City>Houston</City><State>TX</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff15"><OrgName>Max-Planck Institute of Computer Science</OrgName><OrgAddress><City>Saarbrücken</City><Country>Germany</Country></OrgAddress></Affiliation></EditorGroup></SeriesHeader><Book Language="En"><BookInfo BookProductType="Proceedings" ContainsESM="No" Language="En" MediaType="eBook" NumberingDepth="2" NumberingStyle="ContentOnly" OutputMedium="All" TocLevels="0"><BookID>978-3-642-21458-5</BookID><BookTitle>Combinatorial Pattern Matching</BookTitle><BookSubTitle>22nd Annual Symposium, CPM 2011, Palermo, Italy, June 27-29, 2011. Proceedings</BookSubTitle><BookVolumeNumber>6661</BookVolumeNumber><BookSequenceNumber>6661</BookSequenceNumber><BookDOI>10.1007/978-3-642-21458-5</BookDOI><BookTitleID>270808</BookTitleID><BookPrintISBN>978-3-642-21457-8</BookPrintISBN><BookElectronicISBN>978-3-642-21458-5</BookElectronicISBN><BookChapterCount>39</BookChapterCount><BookCopyright><CopyrightHolderName>Springer Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2011</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I16021" Priority="1" Type="Secondary">Algorithm Analysis and Problem Complexity</BookSubject><BookSubject Code="I15017" Priority="2" Type="Secondary">Data Structures</BookSubject><BookSubject Code="I18030" Priority="3" Type="Secondary">Data Mining and Knowledge Discovery</BookSubject><BookSubject Code="I2203X" Priority="4" Type="Secondary">Pattern Recognition</BookSubject><BookSubject Code="I23050" Priority="5" Type="Secondary">Computational Biology/Bioinformatics</BookSubject><BookSubject Code="L15001" Priority="6" Type="Secondary">Bioinformatics</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup><BookContext><SeriesID>558</SeriesID></BookContext></BookInfo><BookHeader><EditorGroup><Editor AffiliationIDS="Aff16"><EditorName DisplayOrder="Western"><GivenName>Raffaele</GivenName><FamilyName>Giancarlo</FamilyName></EditorName><Contact><Email>raffaele@mfn.unipmn.it</Email></Contact></Editor><Editor AffiliationIDS="Aff17"><EditorName DisplayOrder="Western"><GivenName>Giovanni</GivenName><FamilyName>Manzini</FamilyName></EditorName><Contact><Email>manzini@mfn.unipmn.it</Email></Contact></Editor><Affiliation ID="Aff16"><OrgDivision>Department of Mathematics</OrgDivision><OrgName>Università degli Studi di Palermo</OrgName><OrgAddress><Street>Via Archirafi 34</Street><Postcode>90123</Postcode><City>Palermo</City><Country>Italy</Country></OrgAddress></Affiliation><Affiliation ID="Aff17"><OrgDivision>Department of Computer Science</OrgDivision><OrgName>University of ’Piemonte Orientale’</OrgName><OrgAddress><Street>Viale T. Michel 11</Street><Postcode>15121</Postcode><City>Alessandria</City><Country>Italy</Country></OrgAddress></Affiliation></EditorGroup></BookHeader><Part ID="Part2"><PartInfo TocLevels="0"><PartID>2</PartID><PartSequenceNumber>2</PartSequenceNumber><PartTitle>Contributed Papers</PartTitle><PartChapterCount>36</PartChapterCount><PartContext><SeriesID>558</SeriesID><BookTitle>Combinatorial Pattern Matching</BookTitle></PartContext></PartInfo><Chapter ID="Chap30" Language="En"><ChapterInfo ChapterType="OriginalPaper" ContainsESM="No" NumberingDepth="2" NumberingStyle="ContentOnly" TocLevels="0"><ChapterID>30</ChapterID><ChapterDOI>10.1007/978-3-642-21458-5_30</ChapterDOI><ChapterSequenceNumber>30</ChapterSequenceNumber><ChapterTitle Language="En">Efficient Seeds Computation Revisited</ChapterTitle><ChapterFirstPage>350</ChapterFirstPage><ChapterLastPage>363</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2011</CopyrightYear></ChapterCopyright><ChapterGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><PartID>2</PartID><BookID>978-3-642-21458-5</BookID><BookTitle>Combinatorial Pattern Matching</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff18"><AuthorName DisplayOrder="Western"><GivenName>Michalis</GivenName><FamilyName>Christou</FamilyName></AuthorName><Contact><Email>michalis.christou@dcs.kcl.ac.uk</Email></Contact></Author><Author AffiliationIDS="Aff18 Aff20"><AuthorName DisplayOrder="Western"><GivenName>Maxime</GivenName><FamilyName>Crochemore</FamilyName></AuthorName><Contact><Email>maxime.crochemore@dcs.kcl.ac.uk</Email></Contact></Author><Author AffiliationIDS="Aff18 Aff21"><AuthorName DisplayOrder="Western"><GivenName>Costas</GivenName><GivenName>S.</GivenName><FamilyName>Iliopoulos</FamilyName></AuthorName><Contact><Email>csi@dcs.kcl.ac.uk</Email></Contact></Author><Author AffiliationIDS="Aff19"><AuthorName DisplayOrder="Western"><GivenName>Marcin</GivenName><FamilyName>Kubica</FamilyName></AuthorName><Contact><Email>kubica@mimuw.edu.pl</Email></Contact></Author><Author AffiliationIDS="Aff18"><AuthorName DisplayOrder="Western"><GivenName>Solon</GivenName><GivenName>P.</GivenName><FamilyName>Pissis</FamilyName></AuthorName><Contact><Email>solon.pissis@dcs.kcl.ac.uk</Email></Contact></Author><Author AffiliationIDS="Aff19"><AuthorName DisplayOrder="Western"><GivenName>Jakub</GivenName><FamilyName>Radoszewski</FamilyName></AuthorName><Contact><Email>jrad@mimuw.edu.pl</Email></Contact></Author><Author AffiliationIDS="Aff19 Aff22"><AuthorName DisplayOrder="Western"><GivenName>Wojciech</GivenName><FamilyName>Rytter</FamilyName></AuthorName><Contact><Email>rytter@mimuw.edu.pl</Email></Contact></Author><Author AffiliationIDS="Aff19"><AuthorName DisplayOrder="Western"><GivenName>Bartosz</GivenName><FamilyName>Szreder</FamilyName></AuthorName><Contact><Email>szreder@mimuw.edu.pl</Email></Contact></Author><Author AffiliationIDS="Aff19"><AuthorName DisplayOrder="Western"><GivenName>Tomasz</GivenName><FamilyName>Waleń</FamilyName></AuthorName><Contact><Email>walen@mimuw.edu.pl</Email></Contact></Author><Affiliation ID="Aff18"><OrgDivision>Dept. of Informatics</OrgDivision><OrgName>King’s College London</OrgName><OrgAddress><City>London</City><Postcode>WC2R 2LS</Postcode><Country>UK</Country></OrgAddress></Affiliation><Affiliation ID="Aff19"><OrgDivision>Dept. of Mathematics, Computer Science and Mechanics</OrgDivision><OrgName>University of Warsaw</OrgName><OrgAddress><City>Warsaw</City><Country>Poland</Country></OrgAddress></Affiliation><Affiliation ID="Aff20"><OrgName>Université Paris-Est</OrgName><OrgAddress><Country>France</Country></OrgAddress></Affiliation><Affiliation ID="Aff21"><OrgDivision>Digital Ecosystems & Business Intelligence Institute</OrgDivision><OrgName>Curtin University of Technology</OrgName><OrgAddress><City>Perth</City><State>WA</State><Postcode>6845</Postcode><Country>Australia</Country></OrgAddress></Affiliation><Affiliation ID="Aff22"><OrgDivision>Dept. of Math. and Informatics</OrgDivision><OrgName>Copernicus University</OrgName><OrgAddress><City>Toruń</City><Country>Poland</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>The notion of the cover is a generalization of a period of a string, and there are linear time algorithms for finding the shortest cover. The seed is a more complicated generalization of periodicity, it is a cover of a superstring of a given string, and the shortest seed problem is of much higher algorithmic difficulty. The problem is not well understood, no linear time algorithm is known. In the paper we give linear time algorithms for some of its versions — computing shortest left-seed array, longest left-seed array and checking for seeds of a given length. The algorithm for the last problem is used to compute the seed array of a string (i.e., the shortest seeds for all the prefixes of the string) in <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis><Superscript>2</Superscript>) time. We describe also a simpler alternative algorithm computing efficiently the shortest seeds. As a by-product we obtain an <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis>log(<Emphasis Type="Italic">n</Emphasis>/<Emphasis Type="Italic">m</Emphasis>)) time algorithm checking if the shortest seed has length at least <Emphasis Type="Italic">m</Emphasis> and finding the corresponding seed. We also correct some important details missing in the previously known shortest-seed algorithm (Iliopoulos et al., 1996).</Para></Abstract><ArticleNote Type="Misc"><SimplePara>The authors thank an anonymous referee for proposing several insightful remarks.</SimplePara></ArticleNote></ChapterHeader><NoBody></NoBody></Chapter></Part></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Efficient Seeds Computation Revisited</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>Efficient Seeds Computation Revisited</title></titleInfo><name type="personal"><namePart type="given">Michalis</namePart><namePart type="family">Christou</namePart><affiliation>Dept. of Informatics, King’s College London, WC2R 2LS, London, UK</affiliation><affiliation>E-mail: michalis.christou@dcs.kcl.ac.uk</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Maxime</namePart><namePart type="family">Crochemore</namePart><affiliation>Dept. of Informatics, King’s College London, WC2R 2LS, London, UK</affiliation><affiliation>Université Paris-Est, France</affiliation><affiliation>E-mail: maxime.crochemore@dcs.kcl.ac.uk</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Costas</namePart><namePart type="given">S.</namePart><namePart type="family">Iliopoulos</namePart><affiliation>Dept. of Informatics, King’s College London, WC2R 2LS, London, UK</affiliation><affiliation>Digital Ecosystems & Business Intelligence Institute, Curtin University of Technology, 6845, Perth, WA, Australia</affiliation><affiliation>E-mail: csi@dcs.kcl.ac.uk</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Marcin</namePart><namePart type="family">Kubica</namePart><affiliation>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</affiliation><affiliation>E-mail: kubica@mimuw.edu.pl</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Solon</namePart><namePart type="given">P.</namePart><namePart type="family">Pissis</namePart><affiliation>Dept. of Informatics, King’s College London, WC2R 2LS, London, UK</affiliation><affiliation>E-mail: solon.pissis@dcs.kcl.ac.uk</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Jakub</namePart><namePart type="family">Radoszewski</namePart><affiliation>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</affiliation><affiliation>E-mail: jrad@mimuw.edu.pl</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Wojciech</namePart><namePart type="family">Rytter</namePart><affiliation>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</affiliation><affiliation>Dept. of Math. and Informatics, Copernicus University, Toruń, Poland</affiliation><affiliation>E-mail: rytter@mimuw.edu.pl</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Bartosz</namePart><namePart type="family">Szreder</namePart><affiliation>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</affiliation><affiliation>E-mail: szreder@mimuw.edu.pl</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Tomasz</namePart><namePart type="family">Waleń</namePart><affiliation>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland</affiliation><affiliation>E-mail: walen@mimuw.edu.pl</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre displayLabel="OriginalPaper" authority="ISTEX" authorityURI="https://content-type.data.istex.fr" type="conference" valueURI="https://content-type.data.istex.fr/ark:/67375/XTP-BFHXPBJJ-3">conference</genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">2011</dateIssued><dateIssued encoding="w3cdtf">2011</dateIssued><copyrightDate encoding="w3cdtf">2011</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><abstract lang="en">Abstract: The notion of the cover is a generalization of a period of a string, and there are linear time algorithms for finding the shortest cover. The seed is a more complicated generalization of periodicity, it is a cover of a superstring of a given string, and the shortest seed problem is of much higher algorithmic difficulty. The problem is not well understood, no linear time algorithm is known. In the paper we give linear time algorithms for some of its versions — computing shortest left-seed array, longest left-seed array and checking for seeds of a given length. The algorithm for the last problem is used to compute the seed array of a string (i.e., the shortest seeds for all the prefixes of the string) in O(n 2) time. We describe also a simpler alternative algorithm computing efficiently the shortest seeds. As a by-product we obtain an O(nlog(n/m)) time algorithm checking if the shortest seed has length at least m and finding the corresponding seed. We also correct some important details missing in the previously known shortest-seed algorithm (Iliopoulos et al., 1996).</abstract><relatedItem type="host"><titleInfo><title>Combinatorial Pattern Matching</title><subTitle>22nd Annual Symposium, CPM 2011, Palermo, Italy, June 27-29, 2011. Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Raffaele</namePart><namePart type="family">Giancarlo</namePart><affiliation>Department of Mathematics, Università degli Studi di Palermo, Via Archirafi 34, 90123, Palermo, Italy</affiliation><affiliation>E-mail: raffaele@mfn.unipmn.it</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Giovanni</namePart><namePart type="family">Manzini</namePart><affiliation>Department of Computer Science, University of ’Piemonte Orientale’, Viale T. Michel 11, 15121, Alessandria, Italy</affiliation><affiliation>E-mail: manzini@mfn.unipmn.it</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" displayLabel="Proceedings" authority="ISTEX" authorityURI="https://publication-type.data.istex.fr" valueURI="https://publication-type.data.istex.fr/ark:/67375/JMC-0G6R5W5T-Z">book-series</genre><originInfo><publisher>Springer</publisher><copyrightDate encoding="w3cdtf">2011</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book-Subject-Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book-Subject-Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I16021">Algorithm Analysis and Problem Complexity</topic><topic authority="SpringerSubjectCodes" authorityURI="I15017">Data Structures</topic><topic authority="SpringerSubjectCodes" authorityURI="I18030">Data Mining and Knowledge Discovery</topic><topic authority="SpringerSubjectCodes" authorityURI="I2203X">Pattern Recognition</topic><topic authority="SpringerSubjectCodes" authorityURI="I23050">Computational Biology/Bioinformatics</topic><topic authority="SpringerSubjectCodes" authorityURI="L15001">Bioinformatics</topic></subject><identifier type="DOI">10.1007/978-3-642-21458-5</identifier><identifier type="ISBN">978-3-642-21457-8</identifier><identifier type="eISBN">978-3-642-21458-5</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">270808</identifier><identifier type="BookID">978-3-642-21458-5</identifier><identifier type="BookChapterCount">39</identifier><identifier type="BookVolumeNumber">6661</identifier><identifier type="BookSequenceNumber">6661</identifier><identifier type="PartChapterCount">36</identifier><part><date>2011</date><detail type="part"><title>Contributed Papers</title></detail><detail type="volume"><number>6661</number><caption>vol.</caption></detail><extent unit="pages"><start>350</start><end>363</end></extent></part><recordInfo><recordOrigin>Springer Berlin Heidelberg, 2011</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">David</namePart><namePart type="family">Hutchison</namePart><affiliation>Lancaster University, Lancaster, UK</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Takeo</namePart><namePart type="family">Kanade</namePart><affiliation>Carnegie Mellon University, Pittsburgh, PA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Josef</namePart><namePart type="family">Kittler</namePart><affiliation>University of Surrey, Guildford, UK</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jon</namePart><namePart type="given">M.</namePart><namePart type="family">Kleinberg</namePart><affiliation>Cornell University, Ithaca, NY, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Friedemann</namePart><namePart type="family">Mattern</namePart><affiliation>ETH Zurich, Zurich, Switzerland</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">John</namePart><namePart type="given">C.</namePart><namePart type="family">Mitchell</namePart><affiliation>Stanford University, Stanford, CA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Moni</namePart><namePart type="family">Naor</namePart><affiliation>Weizmann Institute of Science, Rehovot, Israel</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Oscar</namePart><namePart type="family">Nierstrasz</namePart><affiliation>University of Bern, Bern, Switzerland</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">C.</namePart><namePart type="family">Pandu Rangan</namePart><affiliation>Indian Institute of Technology, Madras, India</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Bernhard</namePart><namePart type="family">Steffen</namePart><affiliation>University of Dortmund, Dortmund, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Madhu</namePart><namePart type="family">Sudan</namePart><affiliation>Massachusetts Institute of Technology, MA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Demetri</namePart><namePart type="family">Terzopoulos</namePart><affiliation>University of California, Los Angeles, CA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Doug</namePart><namePart type="family">Tygar</namePart><affiliation>University of California, Berkeley, CA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Moshe</namePart><namePart type="given">Y.</namePart><namePart type="family">Vardi</namePart><affiliation>Rice University, Houston, TX, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Weikum</namePart><affiliation>Max-Planck Institute of Computer Science, Saarbrücken, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><publisher>Springer</publisher><copyrightDate encoding="w3cdtf">2011</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer Berlin Heidelberg, 2011</recordOrigin></recordInfo></relatedItem><identifier type="istex">6C0A668C2EFEFF27F9DD326D65984E9A158771B3</identifier><identifier type="ark">ark:/67375/1BB-ML8861L6-1</identifier><identifier type="DOI">10.1007/978-3-642-21458-5_30</identifier><identifier type="ChapterID">30</identifier><identifier type="ChapterID">Chap30</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer Berlin Heidelberg, 2011</accessCondition><recordInfo><recordContentSource authority="ISTEX" authorityURI="https://loaded-corpus.data.istex.fr" valueURI="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-3XSW68JL-F">springer</recordContentSource><recordOrigin>Springer-Verlag Berlin Heidelberg, 2011</recordOrigin></recordInfo></mods><json:item><extension>json</extension><original>false</original><mimetype>application/json</mimetype><uri>https://api.istex.fr/document/6C0A668C2EFEFF27F9DD326D65984E9A158771B3/metadata/json</uri></json:item></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001422 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001422 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Asie
|area= AustralieFrV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:6C0A668C2EFEFF27F9DD326D65984E9A158771B3
|texte= Efficient Seeds Computation Revisited
}}
| This area was generated with Dilib version V0.6.33. |  |