Internal Pattern Matching Queries in a Text and Applications

Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń

Type: Preprint

Publication Date: 2014-12-22

Citations: 32

DOI: https://doi.org/10.1137/1.9781611973730.36

Locations

arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Internal Pattern Matching Queries in a Text and Applications	2013	Tomasz Kociumaka Jakub Radoszewski Wojciech Rytter Tomasz Waleń
+	Compressed Indexing for Consecutive Occurrences	2023	Paweł Gawrychowski Garance Gourdel Tatiana Starikovskaya Teresa Anna Steiner
+ PDF Chat	Internal Pattern Matching in Small Space and Applications	2024	Gabriel Bathie Panagiotis Charalampopoulos Tatiana Starikovskaya
+	Optimal Data Structure for Internal Pattern Matching Queries in a Text and Applications.	2013	Tomasz Kociumaka Jakub Radoszewski Wojciech Rytter Tomasz Waleń
+ PDF Chat	Internal Pattern Matching Queries in a Text and Applications	2024	Tomasz Kociumaka Jakub Radoszewski Wojciech Rytter Tomasz Waleń
+ PDF Chat	Pattern Matching on Grammar-Compressed Strings in Linear Time	2022	Moses Ganardi Paweł Gawrychowski
+ PDF Chat	Internal Longest Palindrome Queries in Optimal Time	2023	Kazuki Mitani Takuya Mieno K. Seto Takashi Horiyama
+	Time-Space Tradeoffs for Finding a Long Common Substring	2020	Stav Ben-Nun Shay Golan Tomasz Kociumaka Matan Kraus
+	Time-Space Tradeoffs for Finding a Long Common Substring	2020	Stav Ben-Nun Shay Golan Tomasz Kociumaka Matan Kraus
+	Faster Algorithms for Internal Dictionary Queries	2023	J.J. Dai Qingyu Shi Tingqiang Xu
+ PDF Chat	Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic	2011	Paweł Gawrychowski
+	A Fast and Small Subsampled R-Index.	2021	Dustin Cobas Travis Gagie Gonzalo Navarro
+	Internal Shortest Absent Word Queries in Constant Time and Linear Space	2021	Golnaz Badkobeh Panagiotis Charalampopoulos Dmitry Kosolobov Solon P. Pissis
+	A Fast and Small Subsampled R-index	2021	Dustin Cobas Travis Gagie Gonzalo Navarro
+	Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k-mismatch Matching	2022	Ce Jin Jakob Nogler
+	Counting Distinct Patterns in Internal Dictionary Matching	2020	Panagiotis Charalampopoulos Tomasz Kociumaka Manal Mohamed Jakub Radoszewski Wojciech Rytter Juliusz Straszyński Tomasz Waleń Wiktor Zuba
+	Counting Distinct Patterns in Internal Dictionary Matching	2020	Panagiotis Charalampopoulos Tomasz Kociumaka Manal Mohamed Jakub Radoszewski Wojciech Rytter Juliusz Straszyński Tomasz Waleń Wiktor Zuba
+	Pattern Matching on Grammar-Compressed Strings in Linear Time	2021	Moses Ganardi Paweł Gawrychowski
+	Beating O(nm) in approximate LZW-compressed pattern matching	2013	Paweł Gawrychowski Damian Straszak
+	Computing Matching Statistics on Repetitive Texts	2021	Younan Gao

Works That Cite This (17)

Action	Title	Year	Authors
+ PDF Chat	Resolution of the Burrows-Wheeler Transform Conjecture	2020	Dominik Kempa Tomasz Kociumaka
+ PDF Chat	The “Runs” Theorem	2017	Hideo Bannai I Tomohiro Shunsuke Inenaga Yuto Nakashima Masayuki Takeda Kazuya Tsuruta
+ PDF Chat	Maximal Unbordered Factors of Random Strings	2016	Patrick Hagge Cording Mathias Bæk Tejs Knudsen
+ PDF Chat	Circular Pattern Matching with k Mismatches	2019	Panagiotis Charalampopoulos Tomasz Kociumaka Solon P. Pissis Jakub Radoszewski Wojciech Rytter Juliusz Straszyński Tomasz Waleń Wiktor Zuba
+ PDF Chat	On Maximal Unbordered Factors	2015	Alexander Loptev Grégory Kucherov Tatiana Starikovskaya
+ PDF Chat	Near-Optimal Computation of Runs over General Alphabet via Non-Crossing LCE Queries	2016	Maxime Crochemore Costas S. Iliopoulos Tomasz Kociumaka Ritu Kundu Solon P. Pissis Jakub Radoszewski Wojciech Rytter Tomasz Waleń
+ PDF Chat	Internal Quasiperiod Queries	2020	Maxime Crochemore Costas S. Iliopoulos Jakub Radoszewski Wojciech Rytter Juliusz Straszyński Tomasz Waleń Wiktor Zuba
+ PDF Chat	Internal Dictionary Matching	2021	Panagiotis Charalampopoulos Tomasz Kociumaka Manal Mohamed Jakub Radoszewski Wojciech Rytter Tomasz Waleń
+	Weighted Edit Distance Computation: Strings, Trees, and Dyck	2023	Debarati Das Jacob Gilbert MohammadTaghi Hajiaghayi Tomasz Kociumaka Barna Saha
+ PDF Chat	Near-Optimal Quantum Algorithms for String Problems	2022	Shyan Akmal Ce Jin

Works Cited by This (39)

Action	Title	Year	Authors
+	Combinatorics on words	1984	M. Lothaire
+ PDF Chat	The equation $a^M=b^Nc^P$ in a free group.	1962	Roger C. Lyndon M. P. Schützenberger
+ PDF Chat	Weighted Ancestors in Suffix Trees	2014	Paweł Gawrychowski Moshe Lewenstein Patrick K. Nicholson
+ PDF Chat	Orthogonal Range Searching for Text Indexing	2013	Moshe Lewenstein
+	Sorted Range Reporting Revisited	2013	Gelin Zhou
+ PDF Chat	Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic	2011	Paweł Gawrychowski
+	Cross-document pattern matching	2013	Tsvi Kopelowitz Grégory Kucherov Yakov Nekrich Tatiana Starikovskaya
+ PDF Chat	Uniqueness theorems for periodic functions	1965	N. J. Fine Herbert S. Wilf
+	An application of pattern matching to a problem in geometrical complexity	1976	Glenn K. Manacher
+ PDF Chat	Faster Fully Compressed Pattern Matching by Recompression	2015	Artur Jeż