Shunsuke Inenaga

Dominik Köppl

Florin Manea

Theory Comput. Syst., 2018

Algorithms and combinatorial properties on shortest unique palindromic substrings.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2018

A hardness result and new algorithm for the longest common palindromic subsequence problem.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2018

Dynamic RLE-Compressed Edit Distance Tables Under General Weighted Cost Functions.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2018

Diverse Palindromic Factorization is NP-Complete.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2018

O(n log n)-time Text Compression by LZ-style Longest First Substitution.

[BibT_eX]

[DOI]

Proceedings of the Prague Stringology Conference 2018, 2018

Right-to-left Online Construction of Parameterized Position Heaps.

[BibT_eX]

[DOI]

Proceedings of the Prague Stringology Conference 2018, 2018

Recovering, Counting and Enumerating Strings from Forward and Backward Suffix Arrays.

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2018

Block Palindromes: A New Generalization of Palindromes.

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2018

Longest Lyndon Substring After Edit.

[BibT_eX]

[DOI]

Proceedings of the Annual Symposium on Combinatorial Pattern Matching, 2018

Computing longest common square subsequences.

[BibT_eX]

[DOI]

Proceedings of the Annual Symposium on Combinatorial Pattern Matching, 2018

Lyndon Factorization of Grammar Compressed Texts Revisited.

[BibT_eX]

[DOI]

Proceedings of the Annual Symposium on Combinatorial Pattern Matching, 2018

Longest substring palindrome after edit.

[BibT_eX]

[DOI]

Proceedings of the Annual Symposium on Combinatorial Pattern Matching, 2018

Faster Online Elastic Degenerate String Matching.

[BibT_eX]

[DOI]

Proceedings of the Annual Symposium on Combinatorial Pattern Matching, 2018

2017

Inferring strings from Lyndon factorization.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2017

The "Runs" Theorem.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing.

[BibT_eX]

[DOI]

IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2017

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

[BibT_eX]

[DOI]

CoRR, 2017

Computing Abelian regularities on RLE strings.

[BibT_eX]

[DOI]

CoRR, 2017

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

[BibT_eX]

[DOI]

CoRR, 2017

Efficient Computation of Substring Equivalence Classes with Suffix Arrays.

[BibT_eX]

[DOI]

Algorithmica, 2017

On Reverse Engineering the Lyndon Tree.

[BibT_eX]

[DOI]

Proceedings of the Prague Stringology Conference 2017, 2017

Linear-Size CDAWG: New Repetition-Aware Indexing and Grammar Compression.

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2017

Order Preserving Pattern Matching on Trees and DAGs.

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2017

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

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2017

Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2017: Theory and Practice of Computer Science, 2017

Computing Longest Single-arm-gapped Palindromes in a String.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2017: Theory and Practice of Computer Science, 2017

Small-Space LCE Data Structure with Constant-Time Queries.

[BibT_eX]

[DOI]

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

Computing Abelian String Regularities Based on RLE.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 28th International Workshop, 2017

Shortest Unique Palindromic Substring Queries in Optimal Time.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 28th International Workshop, 2017

Almost Linear Time Computation of Maximal Repetitions in Run Length Encoded Strings.

[BibT_eX]

[DOI]

Proceedings of the 28th International Symposium on Algorithms and Computation, 2017

Tight Bounds on the Maximum Number of Shortest Unique Substrings.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching, 2017

Faster STR-IC-LCS Computation via RLE.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching, 2017

Computing All Distinct Squares in Linear Time for Integer Alphabets.

[BibT_eX]

[DOI]

Hideo Bannai

Dominik Köppl

Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching, 2017

2016

Generalized pattern matching and periodicity under substring consistent equivalence relations.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

Faster Lyndon factorization algorithms for SLP and LZ78 compressed text.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

Closed factorization.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2016

Tight bound on the maximum number of shortest unique substrings.

[BibT_eX]

[DOI]

CoRR, 2016

Computing Smallest and Largest Repetition Factorizations in O(n log n) Time.

[BibT_eX]

[DOI]

Proceedings of the Prague Stringology Conference 2016, 2016

Efficiently Finding All Maximal alpha-gapped Repeats.

[BibT_eX]

[DOI]

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Compacting a Dynamic Edit Distance Table by RLE Compression.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2016: Theory and Practice of Computer Science, 2016

Fully Dynamic Data Structure for LCE Queries in Compressed Space.

[BibT_eX]

[DOI]

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Shortest Unique Substring Queries on Run-Length Encoded Strings.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Finding Gapped Palindromes Online.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 27th International Workshop, 2016

Deterministic Sub-Linear Space LCE Data Structures With Efficient Construction.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching, 2016

Fully-online Construction of Suffix Trees for Multiple Texts.

[BibT_eX]

[DOI]

Takuya Takagi

Hiroki Arimura

Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching, 2016

Factorizing a String into Squares in Linear Time.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching, 2016

2015

Compressed automata for dictionary matching.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

Dynamic edit distance table under a general weighted cost function.

[BibT_eX]

[DOI]

Kazuyuki Narisawa

J. Discrete Algorithms, 2015

Constructing LZ78 tries and position heaps in linear time for large alphabets.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2015

Detecting regularities on grammar-compressed strings.

[BibT_eX]

[DOI]

Inf. Comput., 2015

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

[BibT_eX]

[DOI]

Takuya Takagi

Hiroki Arimura

CoRR, 2015

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

[BibT_eX]

[DOI]

CoRR, 2015

Efficiently Finding All Maximal $α$-gapped Repeats.

[BibT_eX]

[DOI]

CoRR, 2015

Diverse Palindromic Factorization is NP-Complete.

[BibT_eX]

[DOI]

CoRR, 2015

Computing Left-Right Maximal Generic Words.

[BibT_eX]

[DOI]

Proceedings of the Prague Stringology Conference 2015, 2015

A Faster Longest Common Extension Algorithm on Compressed Strings and its Applications.

[BibT_eX]

[DOI]

Proceedings of the Prague Stringology Conference 2015, 2015

A Faster Algorithm for Computing Maximal \alpha -gapped Repeats in a String.

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2015

Efficient Algorithms for Longest Closed Factor Array.

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2015

A new characterization of maximal repetitions by Lyndon trees.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Inferring Strings from Full Abelian Periods.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

Diverse Palindromic Factorization Is NP-complete.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory - 19th International Conference, 2015

Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015

LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015

An Opportunistic Text Indexing Structure Based on Run Length Encoding.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity - 9th International Conference, 2015

2014

Inferring strings from suffix trees and links on a binary alphabet.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2014

Computing Abelian Covers and Abelian Runs.

[BibT_eX]

[DOI]

Proceedings of the Prague Stringology Conference 2014, Prague, Czech Republic, 2014

Faster Compact On-Line Lempel-Ziv Factorization.

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

Shortest Unique Substrings Queries in Optimal Time.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2014: Theory and Practice of Computer Science, 2014

Computing Palindromic Factorizations and Palindromic Covers On-line.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching - 25th Annual Symposium, 2014

2013

Palindrome pattern matching.

[BibT_eX]

[DOI]

Tomohiro I

Theor. Comput. Sci., 2013

Fast q-gram mining on SLP compressed strings.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2013

Foreword.

[BibT_eX]

[DOI]

Carlos Martín-Vide

Int. J. Comput. Math., 2013

Computing Reversed Lempel-Ziv Factorization Online.

[BibT_eX]

[DOI]

Proceedings of the Prague Stringology Conference 2013, Prague, Czech Republic, 2013

Permuted Pattern Matching on Multi-track Strings.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2013: Theory and Practice of Computer Science, 2013

Computing Convolution on Grammar-Compressed Text.

[BibT_eX]

[DOI]

Proceedings of the 2013 Data Compression Conference, 2013

From Run Length Encoding to LZ78 and Back Again.

[BibT_eX]

[DOI]

Proceedings of the 2013 Data Compression Conference, 2013

Efficient Lyndon Factorization of Grammar Compressed Text.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching, 24th Annual Symposium, 2013

Converting SLP to LZ78 in almost Linear Time.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2012

Finding Characteristic Substrings from Compressed Texts.

[BibT_eX]

[DOI]

Hideo Bannai

Int. J. Found. Comput. Sci., 2012

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

[BibT_eX]

[DOI]

CoRR, 2012

The Position Heap of a Trie.

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2012

Efficient LZ78 Factorization of Grammar Compressed Text.

[BibT_eX]

[DOI]

Hideo Bannai

Proceedings of the String Processing and Information Retrieval, 2012

Computing q-Gram Non-overlapping Frequencies on SLP Compressed Texts.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2012: Theory and Practice of Computer Science, 2012

Speeding Up q-Gram Mining on Grammar-Based Compressed Texts.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching - 23rd Annual Symposium, 2012

2011

Verifying and enumerating parameterized border arrays.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

Password Based Anonymous Authentication with Private Information Retrieval.

[BibT_eX]

J. Digit. Inf. Manag., 2011

Missing pattern discovery.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2011

Towards Modeling Stored-value Electronic Money Systems.

[BibT_eX]

[DOI]

Kenichirou Oyama

Hiroto Yasuura

Inf. Media Technol., 2011

Computing q-gram Frequencies on Collage Systems

[BibT_eX]

[DOI]

CoRR, 2011

Restructuring Compressed Texts without Explicit Decompression

[BibT_eX]

[DOI]

CoRR, 2011

Computing Longest Common Substring/Subsequence of Non-linear Texts.

[BibT_eX]

[DOI]

Proceedings of the Prague Stringology Conference 2011, 2011

Faster Subsequence and Don't-Care Pattern Matching on Compressed Texts.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching - 22nd Annual Symposium, 2011

An Anonymous Authentication Protocol with Single-database PIR.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Wataru Matsubara

Chic. J. Theor. Comput. Sci., 2010

Counting and Verifying Maximal Palindromes.

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2010

An Identifiable Yet Unlinkable Authentication System with Smart Cards for Multiple Services.

[BibT_eX]

[DOI]

Proceedings of the Computational Science and Its Applications, 2010

Verifying a Parameterized Border Array in O(n1.5) Time.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching, 21st Annual Symposium, 2010

2009

Efficient algorithms to compute compressed longest common substrings and compressed palindromes.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

Linear-Time Text Compression by Longest-First Substitution.

[BibT_eX]

[DOI]

Algorithms, 2009

Modeling Costs of Access Control with Various Key Management Systems.

[BibT_eX]

Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, 2009

Counting Parameterized Border Arrays for a Binary Alphabet.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2009

Lightweight Parameterized Suffix Array Construction.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms, 20th International Workshop, 2009

Testing Square-Freeness of Strings Compressed by Balanced Straight Line Program.

[BibT_eX]

[DOI]

Wataru Matsubara

Proceedings of the Theory of Computing 2009, 2009

2008

Reachability on Suffix Tree Graphs.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2008

Parameterized Suffix Arrays for Binary Strings.

[BibT_eX]

[DOI]

Proceedings of the Prague Stringology Conference 2008, Prague, Czech Republic, 2008

Computing Longest Common Substring and All Palindromes from Compressed Strings.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2008: Theory and Practice of Computer Science, 2008

String Kernels Based on Variable-Length-Don't-Care Patterns.

[BibT_eX]

[DOI]

Proceedings of the Discovery Science, 11th International Conference, 2008

An Efficient Algorithm to Test Square-Freeness of Strings Compressed by Balanced Straight Line Program.

[BibT_eX]

[DOI]

Wataru Matsubara

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.

[BibT_eX]

[DOI]

Proceedings of the 2007 Data Compression Conference (DCC 2007), 2007

Efficient Computation of Substring Equivalence Classes with Suffix Arrays.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching, 18th Annual Symposium, 2007

2006

Sparse compact directed acyclic word graphs.

[BibT_eX]

[DOI]

Proceedings of the Prague Stringology Conference, 2006

Sparse Directed Acyclic Word Graphs.

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2006

A New Family of String Classifiers Based on Local Relatedness.

[BibT_eX]

[DOI]

Proceedings of the Discovery Science, 9th International Conference, 2006

On-Line Linear-Time Construction of Word Suffix Trees.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching, 17th Annual Symposium, 2006

2005

A fully compressed pattern matching algorithm for simple collage systems.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2005

On-line construction of compact directed acyclic word graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2005

Composite Pattern Discovery for PCR Application.

[BibT_eX]

[DOI]

Stanislav Angelov

Proceedings of the String Processing and Information Retrieval, 2005

Fully Incremental LCS Computation.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

Practical Algorithms for Pattern Based Linear Regression.

[BibT_eX]

[DOI]

Proceedings of the Discovery Science, 8th International Conference, 2005

2004

Ternary directed acyclic word graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2004

Compact directed acyclic word graphs for a sliding window.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2004

Efficiently Finding Regulatory Elements Using Correlation with Gene Expression.

[BibT_eX]

[DOI]

J. Bioinform. Comput. Biol., 2004

Finding Missing Patterns.

[BibT_eX]

[DOI]

Teemu Kivioja

Veli Mäkinen

Proceedings of the Algorithms in Bioinformatics, 4th International Workshop, 2004

An Efficient Pattern Matching Algorithm on a Subclass of Context Free Grammars.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 2004

Finding Optimal Pairs of Cooperative and Competing Patterns with Bounded Distance.

[BibT_eX]

[DOI]

Proceedings of the Discovery Science, 7th International Conference, 2004

2003

Bidirectional Construction of Suffix Trees.

[BibT_eX]