String processing and information retrieval : 28th international symposium, SPIRE 2021, Lille, France, October 4-6, 2021, proceedings

Preface
Organization
Contents
Invited Papers
r-Indexing the eBWT
	1 Introduction
	2 Preliminaries
	3 r-Indexing the eBWT
	4 Constructing the r-Index of the eBWT
	5 Conclusions
	References
Unicode at Gigabytes per Second
	1 Introduction
	2 Related Work
	3 The Unicode Formats
	4 Algorithms
	5 Experiments
	6 Conclusion
	References
Combinatorics
Longest Common Rollercoasters
	1 Introduction
		1.1 Related Work
	2 Preliminaries
	3 Algorithms
		3.1 O(nmk) Time and Space Algorithm
		3.2 O(rklog3 mloglogm) Time and O(rk) Space Algorithm
	4 Conclusion
	References
Minimal Unique Palindromic Substrings After Single-Character Substitution
	1 Introduction
	2 Preliminaries
		2.1 Notations
		2.2 Tools
	3 Changes of MUPSs After Single Character Substitution
	4 Algorithms for Updating Set of MUPSs
		4.1 Computing MUPSs to Be Removed
		4.2 Computing MUPSs to Be Added
	References
Permutation-Constrained Common String Partitions with Applications
	1 Introduction
	2 Preliminary Notions
	3 Reduction to PCSP for Simple String Functions
	4 FPT Algorithms for d-occurrence PCSP with Reversals
		4.1 Bounded Occurrences and Reversal Functions
		4.2 Constructing a Complete and Order-Consistent Fixed-Match Set
	5 Conclusion
	References
All Instantiations of the Greedy Algorithm for the Shortest Common Superstring Problem are Equivalent
	1 Introduction
	2 Preliminaries
	3 Perturbing Procedure
	4 Equivalence of Instantiations
	5 Conclusion
	References
String Covers of a Tree
	1 Introduction
	2 Preliminaries
		2.1 The Table of Prefixes
		2.2 Summing Second Heights of All Nodes
	3 Covers of Directed Trees
	4 Covers of Undirected Trees
		4.1 O(n2) Time and Space Solution
		4.2 O(n2 logn) Time and O(n) Space
	References
Compression
Grammar Index by Induced Suffix Sorting
	1 Introduction
		1.1 Our Contribution
		1.2 Related Work
	2 Preliminaries
		2.1 Induced Suffix Sorting
		2.2 Constructing the Grammar
	3 GCIS Index
	4 Pattern Matching Algorithm
		4.1 Cores
		4.2 Matching with GST
	5 Implementation and Experiments
	References
An LMS-Based Grammar Self-index with Local Consistency Properties
	1 Introduction
	2 Related Concepts
		2.1 Grammar Compression
		2.2 A Grammar Self-index
		2.3 Locally Consistent Parsing
		2.4 Locally Consistent Grammars
		2.5 Induced Suffix Sorting
	3 A Grammar Self-index Based on LMS Parsing
		3.1 LMS Parsing
		3.2 Computing the Cuts During the Pattern Matching
	4 Experiments
	5 Results and Discussion
	6 Concluding Remarks
	References
On the Approximation Ratio of LZ-End to LZ77
	1 Introduction
	2 Preliminaries
		2.1 Strings
		2.2 Lempel-Ziv Factorizations
		2.3 Period-Doubling Sequence
	3 Properties on Period-Doubling Sequence
	4 Factorizations of Period-Doubling Sequence
	5 Conclusions and Further Work
	References
Data Structures
Computing the Original eBWT Faster, Simpler, and with Less Memory
	1 Introduction
	2 Preliminaries
	3 Computing the eBWT and GCA
	4 eBWT and PFP
	5 Results and Discussion
	References
Extracting the Sparse Longest Common Prefix Array from the Suffix Binary Search Tree
	1 Introduction
	2 Preliminaries
	3 The Suffix AVL Tree
	4 Computing the Sparse LCP Array
	5 Future Work
	References
findere: Fast and Precise Approximate Membership Query
	1 Introduction
	2 Method
		2.1 Background
		2.2 Decreasing the AMQ False-Positive Rate with ``Query Time Filtration''
		2.3 Querying K-mers with findere
	3 Results
		3.1 Experimental Data
		3.2 Results on Genomics Data
		3.3 Results on Natural Languages
		3.4 Limit of the findere Approach
	4 Conclusion
	References
Repeats
A Separation of  and b via Thue–Morse Words
	1 Introduction
	2 Preliminaries
	3 Important Characteristics of Thue–Morse Words
	4 Upper and Lower Bounds on b
		4.1 Upper Bound
		4.2 Lower Bound
	5 Conclusion
	References
Lower Bounds for the Number of Repetitions in 2D Strings
	1 Introduction
	2 Preliminaries
	3 Distinct Tandems
	4 Distinct Quartics
		4.1 Construction
		4.2 Analysis
		4.3 Reducing the Alphabet
	5 Runs
		5.1 Construction
		5.2 Analysis
	References
On Stricter Reachable Repetitiveness Measures
	1 Introduction
	2 Basic Concepts
		2.1 Terminology
		2.2 Parsing Based Schemes
		2.3 Grammars and Generalizations
		2.4 Lower Bounds
		2.5 Morphisms over Strings
	3 Macro Systems
	4 Deterministic Lindenmayer Systems
	5 NU-Systems
	6 Future Work
	7 Conclusions
	References
Information Retrieval
Improved Topic Modeling in Twitter Through Community Pooling
	1 Introduction
	2 Tweet Pooling for Topic Models
	3 Twitter Dataset Construction
	4 Evaluation
	5 Results
	6 Conclusions
	References
TSXor: A Simple Time Series Compression Algorithm
	1 Introduction
	2 Background
	3 TSXor
	4 Experiments
	5 Conclusion and Future Work
	References
Pattern Matching
Exploiting Pseudo-locality of Interchange Distance
	1 Introduction
	2 Preliminaries
	3 Approximate NN-Search in High Dimensional Spaces
	4 Approximate Pattern Matching
	5 Conclusion and Open Problems
	References
Position Heaps for Cartesian-Tree Matching on Strings and Tries
	1 Introduction
	2 Preliminaries
		2.1 Strings and (Reversed) Tries
		2.2 Cartesian-Tree Pattern Matching
		2.3 Sequence Hash Trees
	3 Cartesian-Tree Position Heaps for Strings
	4 Cartesian-Tree Position Heaps for Tries
	5 Cartesian-Tree Pattern Matching with Position Heaps
		5.1 Pattern Matching on Text String S with CPH(S)
		5.2 Pattern Matching on Text Trie  with
	References
Author Index