# Shunsuke Inenaga

According to our database1, Shunsuke Inenaga authored at least 178 papers between 2001 and 2021.

Collaborative distances:
• Dijkstra number2 of four.
• Erdős number3 of four.

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2021
The Smallest Grammar Problem Revisited.
IEEE Trans. Inf. Theory, 2021

2020
Efficient computation of longest single-arm-gapped palindromes in a string.
Theor. Comput. Sci., 2020

Space-efficient algorithms for computing minimal/shortest unique substrings.
Theor. Comput. Sci., 2020

Fast Algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded Strings.
Theory Comput. Syst., 2020

Dynamic index and LZ factorization in compressed space.
Discret. Appl. Math., 2020

The Parameterized Suffix Tray.
CoRR, 2020

Novel Results on the Number of Runs of the Burrows-Wheeler-Transform.
CoRR, 2020

Computing Palindromic Trees for a Sliding Window and Its Applications.
CoRR, 2020

Grammar-compressed Self-index with Lyndon Words.
CoRR, 2020

Practical Grammar Compression Based on Maximal Repeats.
Algorithms, 2020

Fully-Online Suffix Tree and Directed Acyclic Word Graph Construction for Multiple Texts.
Algorithmica, 2020

Pointer-Machine Algorithms for Fully-Online Construction of Suffix Trees and DAWGs on Multiple Strings.
Proceedings of the Prague Stringology Conference 2020, Prague, Czech Republic, August 31, 2020

Towards Efficient Interactive Computation of Dynamic Time Warping Distance.
Proceedings of the String Processing and Information Retrieval, 2020

On Repetitiveness Measures of Thue-Morse Words.
Proceedings of the String Processing and Information Retrieval, 2020

Longest Square Subsequence Problem Revisited.
Proceedings of the String Processing and Information Retrieval, 2020

Faster STR-EC-LCS Computation.
Proceedings of the SOFSEM 2020: Theory and Practice of Computer Science, 2020

Minimal Unique Substrings and Minimal Absent Words in a Sliding Window.
Proceedings of the SOFSEM 2020: Theory and Practice of Computer Science, 2020

Suffix Trees, DAWGs and CDAWGs for Forward and Backward Tries.
Proceedings of the LATIN 2020: Theoretical Informatics, 2020

A Reduction of the Dynamic Time Warping Distance to the Longest Increasing Subsequence Length.
Proceedings of the 31st International Symposium on Algorithms and Computation, 2020

c-Trie++: A Dynamic Trie Tailored for Fast Prefix Searches.
Proceedings of the Data Compression Conference, 2020

DAWGs for Parameterized Matching: Online Construction and Related Indexing Structures.
Proceedings of the 31st Annual Symposium on Combinatorial Pattern Matching, 2020

Detecting k-(Sub-)Cadences and Equidistant Subsequence Occurrences.
Proceedings of the 31st Annual Symposium on Combinatorial Pattern Matching, 2020

2019
On the size of the smallest alphabet for Lyndon trees.
Theor. Comput. Sci., 2019

Efficient dynamic dictionary matching with DAWGs and AC-automata.
Theor. Comput. Sci., 2019

Dynamic Packed Compact Tries Revisited.
CoRR, 2019

Computing Maximal Palindromes and Distinct Palindromes in a Trie.
Proceedings of the Prague Stringology Conference 2019, 2019

<i>k</i>-Abelian Pattern Matching: Revisited, Corrected, and Extended.
Proceedings of the Prague Stringology Conference 2019, 2019

Compact Data Structures for Shortest Unique Substring Queries.
Proceedings of the String Processing and Information Retrieval, 2019

On Longest Common Property Preserved Substring Queries.
Proceedings of the String Processing and Information Retrieval, 2019

Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets.
Proceedings of the String Processing and Information Retrieval, 2019

Shortest Unique Palindromic Substring Queries on Run-Length Encoded Strings.
Proceedings of the Combinatorial Algorithms - 30th International Workshop, 2019

An Improved Data Structure for Left-Right Maximal Generic Words Problem.
Proceedings of the 30th International Symposium on Algorithms and Computation, 2019

MR-RePair: Grammar Compression Based on Maximal Repeats.
Proceedings of the Data Compression Conference, 2019

On the Size of Overlapping Lempel-Ziv and Lyndon Factorizations.
Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching, 2019

Computing Runs on a Trie.
Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching, 2019

Online Algorithms for Constructing Linear-Size Suffix Trie.
Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching, 2019

Faster Queries for Longest Substring Palindrome After Block Edit.
Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching, 2019

The Parameterized Position Heap of a Trie.
Proceedings of the Algorithms and Complexity - 11th International Conference, 2019

2018
Tighter Bounds and Optimal Algorithms for All Maximal α-gapped Repeats and Palindromes - Finding All Maximal α-gapped Repeats and Palindromes in Optimal Worst Case Time on Integer Alphabets.
Theory Comput. Syst., 2018

Algorithms and combinatorial properties on shortest unique palindromic substrings.
J. Discrete Algorithms, 2018

A hardness result and new algorithm for the longest common palindromic subsequence problem.
Inf. Process. Lett., 2018

Dynamic RLE-Compressed Edit Distance Tables Under General Weighted Cost Functions.
Int. J. Found. Comput. Sci., 2018

Diverse Palindromic Factorization is NP-Complete.
Int. J. Found. Comput. Sci., 2018

O(n log n)-time Text Compression by LZ-style Longest First Substitution.
Proceedings of the Prague Stringology Conference 2018, 2018

Right-to-left Online Construction of Parameterized Position Heaps.
Proceedings of the Prague Stringology Conference 2018, 2018

Recovering, Counting and Enumerating Strings from Forward and Backward Suffix Arrays.
Proceedings of the String Processing and Information Retrieval, 2018

Block Palindromes: A New Generalization of Palindromes.
Proceedings of the String Processing and Information Retrieval, 2018

Longest Lyndon Substring After Edit.
Proceedings of the Annual Symposium on Combinatorial Pattern Matching, 2018

Computing longest common square subsequences.
Proceedings of the Annual Symposium on Combinatorial Pattern Matching, 2018

Lyndon Factorization of Grammar Compressed Texts Revisited.
Proceedings of the Annual Symposium on Combinatorial Pattern Matching, 2018

Longest substring palindrome after edit.
Proceedings of the Annual Symposium on Combinatorial Pattern Matching, 2018

Faster Online Elastic Degenerate String Matching.
Proceedings of the Annual Symposium on Combinatorial Pattern Matching, 2018

2017
Inferring strings from Lyndon factorization.
Theor. Comput. Sci., 2017

The "Runs" Theorem.
SIAM J. Comput., 2017

Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing.
IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2017

Small-space encoding LCE data structure with constant-time queries.
CoRR, 2017

Computing Abelian regularities on RLE strings.
CoRR, 2017

On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation.
CoRR, 2017

Efficient Computation of Substring Equivalence Classes with Suffix Arrays.
Algorithmica, 2017

On Reverse Engineering the Lyndon Tree.
Proceedings of the Prague Stringology Conference 2017, 2017

Linear-Size CDAWG: New Repetition-Aware Indexing and Grammar Compression.
Proceedings of the String Processing and Information Retrieval, 2017

Order Preserving Pattern Matching on Trees and DAGs.
Proceedings of the String Processing and Information Retrieval, 2017

On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation.
Proceedings of the String Processing and Information Retrieval, 2017

Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings.
Proceedings of the SOFSEM 2017: Theory and Practice of Computer Science, 2017

Computing Longest Single-arm-gapped Palindromes in a String.
Proceedings of the SOFSEM 2017: Theory and Practice of Computer Science, 2017

Small-Space LCE Data Structure with Constant-Time Queries.
Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

Computing Abelian String Regularities Based on RLE.
Proceedings of the Combinatorial Algorithms - 28th International Workshop, 2017

Shortest Unique Palindromic Substring Queries in Optimal Time.
Proceedings of the Combinatorial Algorithms - 28th International Workshop, 2017

Almost Linear Time Computation of Maximal Repetitions in Run Length Encoded Strings.
Proceedings of the 28th International Symposium on Algorithms and Computation, 2017

Tight Bounds on the Maximum Number of Shortest Unique Substrings.
Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching, 2017

Faster STR-IC-LCS Computation via RLE.
Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching, 2017

Computing All Distinct Squares in Linear Time for Integer Alphabets.
Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching, 2017

2016
Generalized pattern matching and periodicity under substring consistent equivalence relations.
Theor. Comput. Sci., 2016

Faster Lyndon factorization algorithms for SLP and LZ78 compressed text.
Theor. Comput. Sci., 2016

Closed factorization.
Discret. Appl. Math., 2016

Tight bound on the maximum number of shortest unique substrings.
CoRR, 2016

Computing Smallest and Largest Repetition Factorizations in <i>O</i>(<i>n</i> log <i>n</i>) Time.
Proceedings of the Prague Stringology Conference 2016, 2016

Efficiently Finding All Maximal alpha-gapped Repeats.
Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Compacting a Dynamic Edit Distance Table by RLE Compression.
Proceedings of the SOFSEM 2016: Theory and Practice of Computer Science, 2016

Fully Dynamic Data Structure for LCE Queries in Compressed Space.
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Shortest Unique Substring Queries on Run-Length Encoded Strings.
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Computing DAWGs and Minimal Absent Words in Linear Time for Integer Alphabets.
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Finding Gapped Palindromes Online.
Proceedings of the Combinatorial Algorithms - 27th International Workshop, 2016

Deterministic Sub-Linear Space LCE Data Structures With Efficient Construction.
Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching, 2016

Fully-online Construction of Suffix Trees for Multiple Texts.
Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching, 2016

Factorizing a String into Squares in Linear Time.
Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching, 2016

2015
Compressed automata for dictionary matching.
Theor. Comput. Sci., 2015

Dynamic edit distance table under a general weighted cost function.
J. Discrete Algorithms, 2015

Constructing LZ78 tries and position heaps in linear time for large alphabets.
Inf. Process. Lett., 2015

Detecting regularities on grammar-compressed strings.
Inf. Comput., 2015

Fully-online construction of suffix trees and DAWGs for multiple texts.
CoRR, 2015

Dynamic index, LZ factorization, and LCE queries in compressed space.
CoRR, 2015

Efficiently Finding All Maximal $α$-gapped Repeats.
CoRR, 2015

Diverse Palindromic Factorization is NP-Complete.
CoRR, 2015

Computing Left-Right Maximal Generic Words.
Proceedings of the Prague Stringology Conference 2015, 2015

A Faster Longest Common Extension Algorithm on Compressed Strings and its Applications.
Proceedings of the Prague Stringology Conference 2015, 2015

A Faster Algorithm for Computing Maximal \alpha -gapped Repeats in a String.
Proceedings of the String Processing and Information Retrieval, 2015

Efficient Algorithms for Longest Closed Factor Array.
Proceedings of the String Processing and Information Retrieval, 2015

A new characterization of maximal repetitions by Lyndon trees.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Inferring Strings from Full Abelian Periods.
Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

Diverse Palindromic Factorization Is NP-complete.
Proceedings of the Developments in Language Theory - 19th International Conference, 2015

Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree.
Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015

LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding.
Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015

An Opportunistic Text Indexing Structure Based on Run Length Encoding.
Proceedings of the Algorithms and Complexity - 9th International Conference, 2015

2014
Inferring strings from suffix trees and links on a binary alphabet.
Discret. Appl. Math., 2014

Computing Abelian Covers and Abelian Runs.
Proceedings of the Prague Stringology Conference 2014, Prague, Czech Republic, 2014

Faster Compact On-Line Lempel-Ziv Factorization.
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

Shortest Unique Substrings Queries in Optimal Time.
Proceedings of the SOFSEM 2014: Theory and Practice of Computer Science, 2014

Computing Palindromic Factorizations and Palindromic Covers On-line.
Proceedings of the Combinatorial Pattern Matching - 25th Annual Symposium, 2014

2013
Palindrome pattern matching.
Theor. Comput. Sci., 2013

Fast q-gram mining on SLP compressed strings.
J. Discrete Algorithms, 2013

Foreword.
Int. J. Comput. Math., 2013

Computing Reversed Lempel-Ziv Factorization Online.
Proceedings of the Prague Stringology Conference 2013, Prague, Czech Republic, 2013

Permuted Pattern Matching on Multi-track Strings.
Proceedings of the SOFSEM 2013: Theory and Practice of Computer Science, 2013

Computing Convolution on Grammar-Compressed Text.
Proceedings of the 2013 Data Compression Conference, 2013

From Run Length Encoding to LZ78 and Back Again.
Proceedings of the 2013 Data Compression Conference, 2013

Efficient Lyndon Factorization of Grammar Compressed Text.
Proceedings of the Combinatorial Pattern Matching, 24th Annual Symposium, 2013

Converting SLP to LZ78 in almost Linear Time.
Proceedings of the Combinatorial Pattern Matching, 24th Annual Symposium, 2013

2012
An efficient algorithm to test square-freeness of strings compressed by straight-line programs.
Inf. Process. Lett., 2012

Finding Characteristic Substrings from Compressed Texts.
Int. J. Found. Comput. Sci., 2012

Time and Space Efficient Lempel-Ziv Factorization based on Run Length Encoding
CoRR, 2012

The Position Heap of a Trie.
Proceedings of the String Processing and Information Retrieval, 2012

Efficient LZ78 Factorization of Grammar Compressed Text.
Proceedings of the String Processing and Information Retrieval, 2012

Computing q-Gram Non-overlapping Frequencies on SLP Compressed Texts.
Proceedings of the SOFSEM 2012: Theory and Practice of Computer Science, 2012

Speeding Up q-Gram Mining on Grammar-Based Compressed Texts.
Proceedings of the Combinatorial Pattern Matching - 23rd Annual Symposium, 2012

2011
Verifying and enumerating parameterized border arrays.
Theor. Comput. Sci., 2011

Password Based Anonymous Authentication with Private Information Retrieval.
J. Digit. Inf. Manag., 2011

Missing pattern discovery.
J. Discrete Algorithms, 2011

Computing q-gram Frequencies on Collage Systems
CoRR, 2011

Restructuring Compressed Texts without Explicit Decompression
CoRR, 2011

Computing Longest Common Substring/Subsequence of Non-linear Texts.
Proceedings of the Prague Stringology Conference 2011, 2011

Faster Subsequence and Don't-Care Pattern Matching on Compressed Texts.
Proceedings of the Combinatorial Pattern Matching - 22nd Annual Symposium, 2011

An Anonymous Authentication Protocol with Single-database PIR.
Proceedings of the Ninth Australasian Information Security Conference, 2011

2010
An Efficient Algorithm to Test Square-Freeness of Strings Compressed by Balanced Straight Line Programs.
Chic. J. Theor. Comput. Sci., 2010

Counting and Verifying Maximal Palindromes.
Proceedings of the String Processing and Information Retrieval, 2010

An Identifiable Yet Unlinkable Authentication System with Smart Cards for Multiple Services.
Proceedings of the Computational Science and Its Applications, 2010

Verifying a Parameterized Border Array in <i>O</i>(<i>n</i><sup>1.5</sup>) Time.
Proceedings of the Combinatorial Pattern Matching, 21st Annual Symposium, 2010

2009
Efficient algorithms to compute compressed longest common substrings and compressed palindromes.
Theor. Comput. Sci., 2009

Linear-Time Text Compression by Longest-First Substitution.
Algorithms, 2009

Modeling Costs of Access Control with Various Key Management Systems.
Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, 2009

Towards Modeling Stored-value Electronic Money Systems.
Proceedings of the World Congress on Nature & Biologically Inspired Computing, 2009

Counting Parameterized Border Arrays for a Binary Alphabet.
Proceedings of the Language and Automata Theory and Applications, 2009

Lightweight Parameterized Suffix Array Construction.
Proceedings of the Combinatorial Algorithms, 20th International Workshop, 2009

Testing Square-Freeness of Strings Compressed by Balanced Straight Line Program.
Proceedings of the Theory of Computing 2009, 2009

2008
Reachability on Suffix Tree Graphs.
Int. J. Found. Comput. Sci., 2008

Parameterized Suffix Arrays for Binary Strings.
Proceedings of the Prague Stringology Conference 2008, Prague, Czech Republic, 2008

Computing Longest Common Substring and All Palindromes from Compressed Strings.
Proceedings of the SOFSEM 2008: Theory and Practice of Computer Science, 2008

String Kernels Based on Variable-Length-Don't-Care Patterns.
Proceedings of the Discovery Science, 11th International Conference, 2008

An Efficient Algorithm to Test Square-Freeness of Strings Compressed by Balanced Straight Line Program.
Proceedings of the Structure-Based Compression of Complex Massive Data, 22.06., 2008

2007
Simple Linear-Time Off-Line Text Compression by Longest-First Substitution.
Proceedings of the 2007 Data Compression Conference (DCC 2007), 2007

Efficient Computation of Substring Equivalence Classes with Suffix Arrays.
Proceedings of the Combinatorial Pattern Matching, 18th Annual Symposium, 2007

2006
Sparse compact directed acyclic word graphs.
Proceedings of the Prague Stringology Conference, 2006

Sparse Directed Acyclic Word Graphs.
Proceedings of the String Processing and Information Retrieval, 2006

A New Family of String Classifiers Based on Local Relatedness.
Proceedings of the Discovery Science, 9th International Conference, 2006

On-Line Linear-Time Construction of Word Suffix Trees.
Proceedings of the Combinatorial Pattern Matching, 17th Annual Symposium, 2006

2005
A fully compressed pattern matching algorithm for simple collage systems.
Int. J. Found. Comput. Sci., 2005

On-line construction of compact directed acyclic word graphs.
Discret. Appl. Math., 2005

Composite Pattern Discovery for PCR Application.
Proceedings of the String Processing and Information Retrieval, 2005

Fully Incremental LCS Computation.
Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

Practical Algorithms for Pattern Based Linear Regression.
Proceedings of the Discovery Science, 8th International Conference, 2005

2004
Ternary directed acyclic word graphs.
Theor. Comput. Sci., 2004

Compact directed acyclic word graphs for a sliding window.
J. Discrete Algorithms, 2004

Efficiently Finding Regulatory Elements Using Correlation with Gene Expression.
J. Bioinform. Comput. Biol., 2004

Finding Missing Patterns.
Proceedings of the Algorithms in Bioinformatics, 4th International Workshop, 2004

An Efficient Pattern Matching Algorithm on a Subclass of Context Free Grammars.
Proceedings of the Developments in Language Theory, 2004

Finding Optimal Pairs of Cooperative and Competing Patterns with Bounded Distance.
Proceedings of the Discovery Science, 7th International Conference, 2004

2003
Bidirectional Construction of Suffix Trees.
Nord. J. Comput., 2003

A Note on Randomized Algorithm for String Matching with Mismatches.
Nord. J. Comput., 2003

Linear-Time Off-Line Text Compression by Longest-First Substitution.
Proceedings of the String Processing and Information Retrieval, 2003

Inferring Strings from Graphs and Arrays.
Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

Discovering Most Classificatory Patterns for Very Expressive Pattern Classes.
Proceedings of the Discovery Science, 6th International Conference, 2003

2002
Space-Economical Construction of Index Structures for All Suffixes of a String.
Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

Finding Best Patterns Practically.
Proceedings of the Progress in Discovery Science, 2002

Discovering Best Variable-Length-Don't-Care Patterns.
Proceedings of the Discovery Science, 5th International Conference, 2002

The Minimum DAWG for All Suffixes of a String and Its Applications.
Proceedings of the Combinatorial Pattern Matching, 13th Annual Symposium, 2002

2001
Construction of the CDAWG for a Trie.
Proceedings of the Prague Stringology Conference 2001, Prague, Czech Republic, 2001

On-Line Construction of Symmetric Compact Directed Acyclic Word Graphs.
Proceedings of the Eighth International Symposium on String Processing and Information Retrieval, 2001

A Practical Algorithm to Find the Best Episode Patterns.
Proceedings of the Discovery Science, 4th International Conference, DS 2001, Washington, 2001