Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Matthew N. Palmer, Simone Faro, and Stefano Scafiti. Efficient Exact Online String Matching Through Linked Weak Factors. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{palmer_et_al:LIPIcs.SEA.2024.24, author = {Palmer, Matthew N. and Faro, Simone and Scafiti, Stefano}, title = {{Efficient Exact Online String Matching Through Linked Weak Factors}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {24:1--24:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.24}, URN = {urn:nbn:de:0030-drops-203896}, doi = {10.4230/LIPIcs.SEA.2024.24}, annote = {Keywords: String matching, text processing, weak recognition, hashing, experimental algorithms, design and analysis of algorithms} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Panagiotis Charalampopoulos, Paweł Gawrychowski, and Samah Ghazawi. Optimal Bounds for Distinct Quartics. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{charalampopoulos_et_al:LIPIcs.ICALP.2024.39, author = {Charalampopoulos, Panagiotis and Gawrychowski, Pawe{\l} and Ghazawi, Samah}, title = {{Optimal Bounds for Distinct Quartics}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {39:1--39:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.39}, URN = {urn:nbn:de:0030-drops-201823}, doi = {10.4230/LIPIcs.ICALP.2024.39}, annote = {Keywords: 2D strings, quartics, repetitions, periodicity} }
Published in: LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)
Sharma V. Thankachan. Compact Text Indexing for Advanced Pattern Matching Problems: Parameterized, Order-Isomorphic, 2D, etc. (Invited Talk). In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 3:1-3:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{thankachan:LIPIcs.CPM.2022.3, author = {Thankachan, Sharma V.}, title = {{Compact Text Indexing for Advanced Pattern Matching Problems: Parameterized, Order-Isomorphic, 2D, etc.}}, booktitle = {33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)}, pages = {3:1--3:3}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-234-1}, ISSN = {1868-8969}, year = {2022}, volume = {223}, editor = {Bannai, Hideo and Holub, Jan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.3}, URN = {urn:nbn:de:0030-drops-161300}, doi = {10.4230/LIPIcs.CPM.2022.3}, annote = {Keywords: Text Indexing, Suffix Trees, String Matching} }
Published in: LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)
Golnaz Badkobeh, Maxime Crochemore, Jonas Ellert, and Cyril Nicaud. Back-To-Front Online Lyndon Forest Construction. In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 13:1-13:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{badkobeh_et_al:LIPIcs.CPM.2022.13, author = {Badkobeh, Golnaz and Crochemore, Maxime and Ellert, Jonas and Nicaud, Cyril}, title = {{Back-To-Front Online Lyndon Forest Construction}}, booktitle = {33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)}, pages = {13:1--13:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-234-1}, ISSN = {1868-8969}, year = {2022}, volume = {223}, editor = {Bannai, Hideo and Holub, Jan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.13}, URN = {urn:nbn:de:0030-drops-161404}, doi = {10.4230/LIPIcs.CPM.2022.13}, annote = {Keywords: Lyndon factorisation, Lyndon forest, Lyndon table, Lyndon array, right Lyndon tree, Cartesian tree, standard factorisation, online algorithms} }
Published in: LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)
Maxime Crochemore, Costas S. Iliopoulos, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, and Wiktor Zuba. Linear-Time Computation of Shortest Covers of All Rotations of a String. In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{crochemore_et_al:LIPIcs.CPM.2022.22, author = {Crochemore, Maxime and Iliopoulos, Costas S. and Radoszewski, Jakub and Rytter, Wojciech and Straszy\'{n}ski, Juliusz and Wale\'{n}, Tomasz and Zuba, Wiktor}, title = {{Linear-Time Computation of Shortest Covers of All Rotations of a String}}, booktitle = {33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)}, pages = {22:1--22:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-234-1}, ISSN = {1868-8969}, year = {2022}, volume = {223}, editor = {Bannai, Hideo and Holub, Jan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.22}, URN = {urn:nbn:de:0030-drops-161495}, doi = {10.4230/LIPIcs.CPM.2022.22}, annote = {Keywords: cover, quasiperiod, cyclic rotation, seed, run} }
Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Giulia Bernardini, Alberto Marchetti-Spaccamela, Solon P. Pissis, Leen Stougie, and Michelle Sweering. Constructing Strings Avoiding Forbidden Substrings. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bernardini_et_al:LIPIcs.CPM.2021.9, author = {Bernardini, Giulia and Marchetti-Spaccamela, Alberto and Pissis, Solon P. and Stougie, Leen and Sweering, Michelle}, title = {{Constructing Strings Avoiding Forbidden Substrings}}, booktitle = {32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)}, pages = {9:1--9:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-186-3}, ISSN = {1868-8969}, year = {2021}, volume = {191}, editor = {Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.9}, URN = {urn:nbn:de:0030-drops-139604}, doi = {10.4230/LIPIcs.CPM.2021.9}, annote = {Keywords: string algorithms, forbidden strings, de Bruijn graphs, data sanitization} }
Published in: LIPIcs, Volume 128, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)
Mai Alzamel, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, and Wiktor Zuba. Quasi-Linear-Time Algorithm for Longest Common Circular Factor. In 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 128, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{alzamel_et_al:LIPIcs.CPM.2019.25, author = {Alzamel, Mai and Crochemore, Maxime and Iliopoulos, Costas S. and Kociumaka, Tomasz and Radoszewski, Jakub and Rytter, Wojciech and Straszy\'{n}ski, Juliusz and Wale\'{n}, Tomasz and Zuba, Wiktor}, title = {{Quasi-Linear-Time Algorithm for Longest Common Circular Factor}}, booktitle = {30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)}, pages = {25:1--25:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-103-0}, ISSN = {1868-8969}, year = {2019}, volume = {128}, editor = {Pisanti, Nadia and P. Pissis, Solon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.25}, URN = {urn:nbn:de:0030-drops-104961}, doi = {10.4230/LIPIcs.CPM.2019.25}, annote = {Keywords: longest common factor, circular pattern matching, internal pattern matching, intersection of hyperrectangles} }
Published in: LIPIcs, Volume 105, 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018)
Panagiotis Charalampopoulos, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen. Linear-Time Algorithm for Long LCF with k Mismatches. In 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 105, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{charalampopoulos_et_al:LIPIcs.CPM.2018.23, author = {Charalampopoulos, Panagiotis and Crochemore, Maxime and Iliopoulos, Costas S. and Kociumaka, Tomasz and Pissis, Solon P. and Radoszewski, Jakub and Rytter, Wojciech and Walen, Tomasz}, title = {{Linear-Time Algorithm for Long LCF with k Mismatches}}, booktitle = {29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018)}, pages = {23:1--23:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-074-3}, ISSN = {1868-8969}, year = {2018}, volume = {105}, editor = {Navarro, Gonzalo and Sankoff, David and Zhu, Binhai}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2018.23}, URN = {urn:nbn:de:0030-drops-86869}, doi = {10.4230/LIPIcs.CPM.2018.23}, annote = {Keywords: longest common factor, longest common substring, Hamming distance, heavy-light decomposition, difference cover} }
Published in: LIPIcs, Volume 88, 17th International Workshop on Algorithms in Bioinformatics (WABI 2017)
Maxime Crochemore, Alexandre P. Francisco, Solon P. Pissis, and Cátia Vaz. Towards Distance-Based Phylogenetic Inference in Average-Case Linear-Time. In 17th International Workshop on Algorithms in Bioinformatics (WABI 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 88, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{crochemore_et_al:LIPIcs.WABI.2017.9, author = {Crochemore, Maxime and Francisco, Alexandre P. and Pissis, Solon P. and Vaz, C\'{a}tia}, title = {{Towards Distance-Based Phylogenetic Inference in Average-Case Linear-Time}}, booktitle = {17th International Workshop on Algorithms in Bioinformatics (WABI 2017)}, pages = {9:1--9:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-050-7}, ISSN = {1868-8969}, year = {2017}, volume = {88}, editor = {Schwartz, Russell and Reinert, Knut}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2017.9}, URN = {urn:nbn:de:0030-drops-76529}, doi = {10.4230/LIPIcs.WABI.2017.9}, annote = {Keywords: computational biology, phylogenetic inference, Hamming distance} }
Published in: Dagstuhl Reports, Volume 4, Issue 3 (2014)
Maxime Crochemore, James D. Currie, Gregory Kucherov, and Dirk Nowotka. Combinatorics and Algorithmics of Strings (Dagstuhl Seminar 14111). In Dagstuhl Reports, Volume 4, Issue 3, pp. 28-46, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@Article{crochemore_et_al:DagRep.4.3.28, author = {Crochemore, Maxime and Currie, James D. and Kucherov, Gregory and Nowotka, Dirk}, title = {{Combinatorics and Algorithmics of Strings (Dagstuhl Seminar 14111)}}, pages = {28--46}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2014}, volume = {4}, number = {3}, editor = {Crochemore, Maxime and Currie, James D. and Kucherov, Gregory and Nowotka, Dirk}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.3.28}, URN = {urn:nbn:de:0030-drops-45524}, doi = {10.4230/DagRep.4.3.28}, annote = {Keywords: combinatorics on words, string algorithms, automata} }
Published in: Dagstuhl Reports, Volume 1, Issue 2 (2011)
Maxime Crochemore, Lila Kari, Mehryar Mohri, and Dirk Nowotka. Combinatorial and Algorithmic Aspects of Sequence Processing (Dagstuhl Seminar 11081). In Dagstuhl Reports, Volume 1, Issue 2, pp. 47-66, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
@Article{crochemore_et_al:DagRep.1.2.47, author = {Crochemore, Maxime and Kari, Lila and Mohri, Mehryar and Nowotka, Dirk}, title = {{Combinatorial and Algorithmic Aspects of Sequence Processing (Dagstuhl Seminar 11081)}}, pages = {47--66}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2011}, volume = {1}, number = {2}, editor = {Crochemore, Maxime and Kari, Lila and Mohri, Mehryar and Nowotka, Dirk}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.2.47}, URN = {urn:nbn:de:0030-drops-31554}, doi = {10.4230/DagRep.1.2.47}, annote = {Keywords: Combinatorics on words, computational biology, stringology, natural computing, machine learning} }
Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)
Julien Clement, Maxime Crochemore, and Giuseppina Rindone. Reverse Engineering Prefix Tables. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 289-300, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{clement_et_al:LIPIcs.STACS.2009.1825, author = {Clement, Julien and Crochemore, Maxime and Rindone, Giuseppina}, title = {{Reverse Engineering Prefix Tables}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {289--300}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1825}, URN = {urn:nbn:de:0030-drops-18258}, doi = {10.4230/LIPIcs.STACS.2009.1825}, annote = {Keywords: Design and analysis of algorithms, Algorithms on strings, Pattern matching, String matching, Combinatorics on words, Prefix table, Suffix table} }
Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)
Susanne Albers and Pascal Weil. Preface -- 25th International Symposium on Theoretical Aspects of Computer Science. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{albers_et_al:LIPIcs.STACS.2008.1326, author = {Albers, Susanne and Weil, Pascal}, title = {{Preface -- 25th International Symposium on Theoretical Aspects of Computer Science}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {1--10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1326}, URN = {urn:nbn:de:0030-drops-13263}, doi = {10.4230/LIPIcs.STACS.2008.1326}, annote = {Keywords: Symposium, theoretical computer science, algorithms and data structures, automata and formal languages, computational and structural complexity, logic in computer science, applications} }
Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)
Maxime Crochemore and Lucian Ilie. Understanding Maximal Repetitions in Strings. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 11-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{crochemore_et_al:LIPIcs.STACS.2008.1344, author = {Crochemore, Maxime and Ilie, Lucian}, title = {{Understanding Maximal Repetitions in Strings}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {11--16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1344}, URN = {urn:nbn:de:0030-drops-13442}, doi = {10.4230/LIPIcs.STACS.2008.1344}, annote = {Keywords: Combinatorics on words, repetitions in strings, runs, maximal repetitions, maximal periodicities, sum of exponents} }
Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)
Costas S. Iliopoulos, Maxime Crochemore, Marcin Kubica, M. Sohel Rahman, and Tomasz Walen. Improved Algorithms for the Range Next Value Problem and Applications. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 205-216, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{iliopoulos_et_al:LIPIcs.STACS.2008.1359, author = {Iliopoulos, Costas S. and Crochemore, Maxime and Kubica, Marcin and Rahman, M. Sohel and Walen, Tomasz}, title = {{Improved Algorithms for the Range Next Value Problem and Applications}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {205--216}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1359}, URN = {urn:nbn:de:0030-drops-13596}, doi = {10.4230/LIPIcs.STACS.2008.1359}, annote = {Keywords: Algorithms, Data structures} }