Language：English   Publishing type：Research paper (scientific journal)

DOI： 10.3390/electronics11071014

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85126910361&origin=inward

Authorship：Last author,　Corresponding author   Language：English   Publishing type：Research paper (international conference proceedings)

DOI： 10.1109/DCC52660.2022.00032

DOI： 10.1109/DCC52660.2022.00032

Language：English   Publishing type：Research paper (international conference proceedings)

DOI： 10.1109/DCC50243.2021.00027

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85106006610&origin=inward

Authorship：Lead author   Language：English   Publishing type：Research paper (international conference proceedings)

Given a text T of length n, the sparse suffix sorting problem asks for the lexicographic order of suffixes starting at m selectable text positions P. The suffix binary search tree [Irving and Love, JDA’03] is a dynamic data structure that can answer this problem dynamically in the sense that insertions and deletions of positions in P are allowed. While a standard binary search tree on strings needs to store two longest-common prefix (LCP) values per node for providing the same query bounds, each suffix binary search tree node only stores a single LCP value and a bit flag. Its tree topology induces the sorting of the m suffixes by an Euler tour in O(m) time. However, it has not been addressed how to compute the lengths of the longest common prefixes of two suffixes with neighboring ranks with this data structure. We show that we can compute these lengths again by an Euler tour in O(m) time.

DOI： 10.1007/978-3-030-86692-1_12

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85116834863&origin=inward

Authorship：Lead author   Language：English   Publishing type：Research paper (international conference proceedings)

We prove that for n≥ 2, the size b(tn) of the smallest bidirectional scheme for the nth Thue–Morse word tn is n+ 2. Since Kutsukake et al. [SPIRE 2020] show that the size γ(tn) of the smallest string attractor for tn is 4 for n≥ 4, this shows for the first time that there is a separation between the size of the smallest string attractor γ and the size of the smallest bidirectional scheme b, i.e., there exist string families such that γ= o(b).

DOI： 10.1007/978-3-030-86692-1_14

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85116783139&origin=inward

Language：English   Publishing type：Research paper (scientific journal)

DOI： 10.3390/a14010005

Language：English   Publishing type：Research paper (international conference proceedings)

DOI： 10.1007/978-3-030-59212-7_16

Language：English   Publishing type：Research paper (international conference proceedings)

Language：English   Publishing type：Research paper (scientific journal)

DOI： 10.1145/3398681

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85025816771&origin=inward

Authorship：Corresponding author   Language：English   Publishing type：Research paper (scientific journal)

DOI： 10.1016/j.tcs.2019.08.005

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85070385571&origin=inward

Language：English   Publishing type：Research paper (scientific journal)

DOI： 10.1016/j.dam.2019.01.014

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85061439333&origin=inward

Language：English   Publishing type：Research paper (international conference proceedings)

DOI： 10.1007/978-3-030-39881-1_26

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85080940455&origin=inward

Language：English   Publishing type：Research paper (international conference proceedings)

DOI： 10.1007/978-3-030-32686-9_3

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85075670034&origin=inward

Language：English   Publishing type：Research paper (international conference proceedings)

Language：English   Publishing type：Research paper (international conference proceedings)

DOI： 10.1109/DCC.2019.00060

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85066320396&origin=inward

Authorship：Lead author   Language：English   Publishing type：Research paper (scientific journal)

DOI： 10.1016/j.tcs.2018.06.033

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85049535167&origin=inward

Authorship：Corresponding author   Language：English   Publishing type：Research paper (scientific journal)

DOI： 10.1016/j.jda.2018.11.002

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85056312105&origin=inward

Language：English   Publishing type：Research paper (scientific journal)

DOI： 10.1007/s00453-017-0333-1

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85025816771&origin=inward

Authorship：Corresponding author   Language：English   Publishing type：Research paper (international conference proceedings)

DOI： 10.4230/LIPIcs.CPM.2018.7

Scopus

CiNii Research

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85048304169&origin=inward

Language：English   Publishing type：Research paper (international conference proceedings)

DOI： 10.4230/LIPIcs.CPM.2018.24

Scopus

CiNii Research

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85048271134&origin=inward

Language：English   Publishing type：Research paper (international conference proceedings)

DOI： 10.4230/LIPIcs.CPM.2018.9

Scopus

CiNii Research

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85048268511&origin=inward

Language：English   Publishing type：Research paper (scientific journal)

DOI： 10.1007/s00224-017-9794-5

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85028529401&origin=inward

Language：English   Publishing type：Research paper (scientific journal)

DOI： 10.1587/transinf.2017FCP0010

CiNii Article

Other Link： https://ci.nii.ac.jp/naid/130006414054

Authorship：Corresponding author   Language：English   Publishing type：Research paper (international conference proceedings)

DOI： 10.1007/978-3-319-94667-2_27

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85049890021&origin=inward

Language：English   Publishing type：Research paper (international conference proceedings)

DOI： 10.1007/978-3-030-02224-2_18

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85055117003&origin=inward

Authorship：Lead author   Language：English   Publishing type：Research paper (international conference proceedings)

DOI： 10.1007/978-3-319-98654-8_2

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85053865754&origin=inward

Authorship：Corresponding author   Language：English   Publishing type：Research paper (international conference proceedings)

DOI： 10.1007/978-3-030-00479-8_15

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85054822428&origin=inward

Authorship：Corresponding author   Language：English   Publishing type：Research paper (international conference proceedings)

DOI： 10.1007/978-3-319-78825-8_33

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85046002496&origin=inward

Language：English   Publishing type：Research paper (international conference proceedings)

DOI： 10.4230/LIPIcs.ESA.2017.67

Scopus

CiNii Research

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85030564164&origin=inward

Language：English   Publishing type：Research paper (scientific journal)

DOI： 10.1016/j.tcs.2017.05.038

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85020825934&origin=inward

Authorship：Lead author   Language：English   Publishing type：Research paper (international conference proceedings)

DOI： 10.4230/LIPIcs.CPM.2017.18

Scopus

CiNii Research

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85027268431&origin=inward

Authorship：Lead author   Language：English   Publishing type：Research paper (scientific journal)

DOI： 10.1016/j.tcs.2016.03.005

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84961175476&origin=inward

Language：English   Publishing type：Research paper (scientific journal)

DOI： 10.1016/j.dam.2016.04.009

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84967167017&origin=inward

Language：English   Publishing type：Research paper (international conference proceedings)

DOI： 10.4230/LIPIcs.MFCS.2016.72

Scopus

CiNii Research

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85012885943&origin=inward

Language：Japanese   Publishing type：Research paper (scientific journal)

DOI： 10.11517/jsaifpai.101.0_06

CiNii Article

CiNii Research

Other Link： http://id.ndl.go.jp/bib/027587749

Language：English   Publishing type：Research paper (international conference proceedings)

DOI： 10.4230/LIPIcs.CPM.2016.1

Scopus

CiNii Research

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85011977600&origin=inward

Language：English   Publishing type：Research paper (international conference proceedings)

DOI： 10.4230/LIPIcs.STACS.2016.39

Scopus

CiNii Research

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84961615105&origin=inward

Language：English   Publishing type：Research paper (international conference proceedings)

DOI： 10.1007/978-3-662-49529-2_36

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84961711921&origin=inward

Authorship：Corresponding author   Language：English   Publishing type：Research paper (international conference proceedings)

In this paper, we propose a new dynamic compressed index of O(w) space for a dynamic text T, where w = O(min(z logN log-M,N)) is the size of the signature encoding of T, z is the size of the Lempel-Ziv77 (LZ77) factorization of T, N is the length of T, and M ≥ 4N is an integer that can be handled in constant time under word RAM model. Our index supports searching for a pattern P in T in O(|P|fA + log w log |P| log-M(logN + log |P| log-M) + occ logN) time and insertion/deletion of a substring of length y in O((y + logN log-M) log w logN log-M) time, where fA = O(min{log logM log log w log log logM , √ log w log log w}). Also, we propose a new spaceefficient LZ77 factorization algorithm for a given text of length N, which runs in O(NfA + z log w log3 N(log- N)2) time with O(w) working space.

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85027267678&origin=inward

Language：English   Publishing type：Research paper (scientific journal)

© 2015 Elsevier B.V. We present the first worst-case linear-time algorithm to compute the Lempel-Ziv 78 factorization of a given string over an integer alphabet. Our algorithm is based on nearest marked ancestor queries on the suffix tree of the given string. We also show that the same technique can be used to construct the position heap of a set of strings in worst-case linear time, when the set of strings is given as a trie.

DOI： 10.1016/j.ipl.2015.04.002

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84927723236&origin=inward

Language：English   Publishing type：Research paper (scientific journal)

© 2015 Elsevier B.V.. We address a variant of the dictionary matching problem where the dictionary is represented by a straight line program (SLP). For a given SLP-compressed dictionary D of size n and height h representing m patterns of total length N, we present an O(n2log N)-size representation of Aho-Corasick automaton which recognizes all occurrences of the patterns in D in amortized O(h+m) running time per character. We also propose an algorithm to construct this compressed Aho-Corasick automaton in O(n3log n log N) time and O(n2log N) space. In a spacial case where D represents only a single pattern, we present an O(n log N)-size representation of the Morris-Pratt automaton which permits us to find all occurrences of the pattern in amortized O(h) running time per character, and we show how to construct this representation in O(n3log n log N) time with O(n2log N) working space.

DOI： 10.1016/j.tcs.2015.01.019

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84951866541&origin=inward

Authorship：Lead author   Language：English   Publishing type：Research paper (international conference proceedings)

DOI： 10.1016/j.ic.2014.09.009

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85027953511&origin=inward

Language：English   Publishing type：Research paper (international conference proceedings)

© Springer International Publishing Switzerland 2015. We present a compact semi-dynamic text index which allows us to find short patterns efficiently. For parameters k ≤ q ≤ logσ n − logσ logσ n and alphabet size σ = O(polylog(n)), all occ occurrences of a pattern of length at most q−k+1 can be obtained in O(k×occ +logσ n) time, where n is the length of the text. Adding characters to the end of the text is supported in amortized constant time. Our index requires (n/k) log(n/k) + n log σ + o(n) bits of space, which is compact (i.e., O(n log σ)) when k = Θ(logσ n). As a byproduct, we present a succinct van Emde Boas tree which supports insertion, deletion, predecessor, and successor on a dynamic set of integers over the universe [0,m − 1] in O(log logm) time and requires only m + o(m) bits of space.

DOI： 10.1007/978-3-319-19929-0_30

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84948993636&origin=inward

Language：English   Publishing type：Research paper (international conference proceedings)

© Springer International Publishing Switzerland 2015. For both the Lempel Ziv 77- and 78-factorization we propose factorization algorithms using (1 + ε)n lg n + O(n) bits (for any positive constant ε ≤ 1) working space (including the space for the output) for any text of size n over an integer alphabet in O(n/ε2) time.

DOI： 10.1007/978-3-319-19929-0_15

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84948952875&origin=inward

Language：English   Publishing type：Research paper (international conference proceedings)

© Springer International Publishing Switzerland 2015. A string x = uvu with both u, v being non-empty is called a gapped repeat with period p = |uv|, and is denoted by pair (x, p). If p ≤ α(|x| − p) with α > 1, then (x, p) is called an α-gapped repeat. An occurrence [i, i+|x|−1] of an α-gapped repeat (x, p) in a string w is called a maximal α-gapped repeat of w, if it cannot be extended either to the left or to the right in w with the same period p. Kolpakov et al. (CPM 2014) showed that, given a string of length n over a constant alphabet, all the occurrences of maximal α-gapped repeats in the string can be computed in O(α2n+occ) time, where occ is the number of occurrences. In this paper, we propose a faster O(αn + occ)-time algorithm to solve this problem, improving the result of Kolpakov et al. by a factor of α.

DOI： 10.1007/978-3-319-23826-5_13

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84944682942&origin=inward

Language：English   Publishing type：Research paper (international conference proceedings)

Copyright © 2015 by the Society for Industrial and Applied Mathmatics. We give a new characterization of maximal repetitions (or runs) in strings, using a tree defined on recursive standard factorizations of Lyndon words, called the Lyndon tree. The characterization leads to a remarkably simple novel proof of the linearity of the maximum number of runs p(n) in a string of length n. Furthermore, we show an upper bound of p(n) < 1.5n, which improves on the best upper bound 1.6n (Crochemore & Hie 2008) that does not rely on computational verification. The proof also gives rise to a new, conceptually simple linear-time algorithm for computing all the runs in a string. A notable characteristic of our algorithm is that, unlike all existing linear-time algorithms, it does not utilize the Lempel-Ziv factorization of the string.

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84938221386&origin=inward

Language：English   Publishing type：Research paper (international conference proceedings)

© Springer International Publishing Switzerland 2015. We study the sequence of Fibonacci words and some of its derivatives with respect to their suffix array, inverse suffix array and Burrows-Wheeler transform based on the respective suffix array.We show that the suffix array is a rotation of its inverse under certain conditions, and that the factors of the LZ77 factorization of any Fibonacci word yield again similar characteristics.

DOI： 10.1007/978-3-319-23660-5_12

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84945955196&origin=inward

Language：English   Publishing type：Research paper (international conference proceedings)

© Springer International Publishing Switzerland 2015. In [3], a short and elegant proof was presented showing that a word of length n contains at most n - 3 runs. Here we show, using the same technique and a computer search, that the number of runs in a binary word of length n is at most 22/23n < 0.957n.

DOI： 10.1007/978-3-319-23826-5_27

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84944682455&origin=inward

Language：English   Publishing type：Research paper (international conference proceedings)

© Springer-Verlag Berlin Heidelberg 2015. Strings u, v are said to be Abelian equivalent if u is a permutation of the characters appearing in v. A string w is said to have a full Abelian period p if w = w1 …wk, where all wi’s are of length p each and are all Abelian equivalent. This paper studies reverse-engineering problems on full Abelian periods. Given a positive integer n and a set D of divisors of n, we show how to compute in O(n) time the lexicographically smallest string of length n which has all elements of D as its full Abelian periods and has the minimum number of full Abelian periods not in D. Moreover, we give an algorithm to enumerate all such strings in amortized constant time per output after O(n)-time preprocessing. Also, we show how to enumerate the strings which have all elements of D as its full Abelian periods in amortized constant time per output after O(n)-time preprocessing.

DOI： 10.1007/978-3-662-48971-0_64

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84951950947&origin=inward

Authorship：Lead author   Language：English   Publishing type：Research paper (international conference proceedings)

© Tomohiro I, Juha Kärkkäinen, and Dominik Kempa. The sparse suffix sorting problem is to sort b = o(n) arbitrary suffixes of a string of length n using o(n) words of space in addition to the string. We present an O(n) time Monte Carlo algorithm using O(b log b) space and an O(n log b) time Las Vegas algorithm using O(b) space. This is a significant improvement over the best prior solutions by Bille et al. (ICALP 2013): a Monte Carlo algorithm running in O(n log b) time and O(b1+ε) space or O(n log2b) time and O(b) space, and a Las Vegas algorithm running in O(n log2b+b2log b) time and O(b) space. All the above results are obtained with high probability not just in expectation.

DOI： 10.4230/LIPIcs.STACS.2014.386

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84907811406&origin=inward

Language：English   Publishing type：Research paper (international conference proceedings)

© Jun'ichi Yamamoto, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda. We present a new on-line algorithm for computing the Lempel-Ziv factorization of a string that runs in O(N logN) time and uses only O(N log σ) bits of working space, where N is the length of the string and σ is the size of the alphabet. This is a notable improvement compared to the performance of previous on-line algorithms using the same order of working space but running in either O(N log3N) time (Okanohara & Sadakane 2009) or O(N log2N) time (Starikovskaya 2012). The key to our new algorithm is in the utilization of an elegant but less popular index structure called Directed Acyclic Word Graphs, or DAWGs (Blumer et al. 1985). We also present an opportunistic variant of our algorithm, which, given the run length encoding of size m of a string of length N, computes the Lempel-Ziv factorization of the string on-line, in O (m · min{n (log logm)(log logN)/log log logN , √ logm/log logm o})time and O(mlogN) bits of space.

DOI： 10.4230/LIPIcs.STACS.2014.675

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84907858098&origin=inward

Authorship：Lead author   Language：English   Publishing type：Research paper (scientific journal)

A suffix tree, which provides us with a linear space full-text index of a given string, is a fundamental data structure for string processing and information retrieval. In this paper we consider the reverse engineering problem on suffix trees: given an unlabeled ordered rooted tree T accompanied with a node-to-node transition function f, infer a string whose suffix tree and its suffix links for inner nodes are isomorphic to T and f, respectively. Also, we consider the enumeration problem in which we enumerate all strings corresponding to an input tree and links. By introducing new characterizations of suffix trees, we show that the reverse engineering problem and the enumeration problem on suffix trees on a binary alphabet can be solved in optimal time. © 2013 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2013.02.033

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84889665144&origin=inward

Language：English   Publishing type：Research paper (international conference proceedings)

© Czech Technical University in Prague, Czech Republic. A closed string is a string with a proper substring that occurs in the string as a prefix and a suffix, but not elsewhere. Closed strings were introduced by Fici (Proc. WORDS, 2011) as objects of combinatorial interest in the study of Trapezoidal and Sturmian words. In this paper we consider algorithms for computing closed factors (substrings) in strings, and in particular for greedily factorizing a string into a sequence of longest closed factors. We describe an algorithm for this problem that uses linear time and space. We then consider the related problem of computing, for every position in the string, the longest closed factor starting at that position. We describe a simple algorithm for the problem that runs in O(n log n/ log log n) time.

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84928791807&origin=inward

Language：English   Publishing type：Research paper (international conference proceedings)

A palindromic factorization of a string w is a factorization of w consisting only of palindromic substrings of w. In this paper, we present an on-line O(n logn)-time O(n)-space algorithm to compute smallest palindromic factorizations of all prefixes of w, where n is the length of a given string w. We then show how to extend this algorithm to compute smallest maximal palindromic factorizations of all prefixes of w, consisting only of maximal palindromes (non-extensible palindromic substring) of each prefix, in O(n logn) time and O(n) space, in an on-line manner. We also present an on-line O(n)-time O(n)-space algorithm to compute a smallest palindromic cover of w. © 2014 Springer International Publishing Switzerland.

DOI： 10.1007/978-3-319-07566-2_16

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84958527699&origin=inward

Language：English   Publishing type：Research paper (international conference proceedings)

DOI： 10.1007/978-3-662-44465-8_48

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84906230308&origin=inward