記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.dam.2019.01.014

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

A palindrome is a string that reads the same forward and backward. A palindromic substring P of a string S is called a shortest unique palindromic substring (SUPS) for an interval [s,t] in S, if P occurs exactly once in S, this occurrence of P contains interval [s,t], and every palindromic substring of S which contains interval [s,t] and is shorter than P occurs at least twice in S. The SUPS problem is, given a string S, to preprocess S so that for any subsequent query interval [s,t] all the SUPSs for interval [s,t] can be answered quickly. We present an optimal solution to this problem. Namely, we show how to preprocess a given string S of length n in O(n) time and space so that all SUPSs for any subsequent query interval can be answered in O(α+1) time, where α is the number of outputs. We also discuss the number of SUPSs in a string.

DOI： 10.1016/j.jda.2018.11.009

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Kim and Park [A dynamic edit distance table, J. Disc. Algo., 2:302-312, 2004] proposed a method (KP) based on a "dynamic edit distance table" that allows one to efficiently maintain unit cost edit distance information between two strings A of length m and B of length n when the strings can be modified by single-character edits to their left or right ends. This type of computation is useful e.g. in cyclic string comparison. KP uses linear time, O(m + n), to update the distance representation after each single edit. Recently Hyyrö et al. [Incremental string comparison, J. Disc. Algo., 34:2-17, 2015] presented an efficient method for maintaining the dynamic edit distance table under general weighted edit distance, running in O(c(m + n)) time per single edit, where c is the maximum weight of the cost function. The work noted that the Θ(mn) space requirement, and not the running time, may be the main bottleneck in using the dynamic edit distance table. In this paper we take the first steps towards reducing the space usage of the dynamic edit distance table by RLE compressing A and B. Let M and N be the lengths of RLE compressed versions of A and B, respectively. We propose how to store the dynamic edit distance table using Θ(mN + Mn) space while maintaining the same time complexity as the previous methods for uncompressed strings.

DOI： 10.1142/S0129054118410083

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1142/S0129054118400014

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： http://dx.doi.org/10.1142/S0129054118400014

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.ipl.2017.08.006

記述言語：英語   掲載種別：研究論文（学術雑誌）  

We consider the problem of reverse-engineering the Lyndon tree, i.e., given a full binary ordered tree T with n leaves as input, we are to compute a string w of length n of which Lyndon tree is isomorphic to the input tree T. Hereby we call such a string a solution string. Although the problem is easily solvable in linear time for binary alphabets and unbounded-size alphabets, it is not known how to efficiently find the smallest alphabet size for a solution string. In this paper, we show several new observations concerning this problem. Namely, we show that: 1) For any positive integer n, there exists a full binary ordered tree T with n leaves, s.t. the smallest alphabet size of a solution string for T is ⌊[Formula presented]⌋+1. 2) For any full binary ordered tree T with n leaves, there exists a solution string w over an alphabet of size at most ⌊[Formula presented]⌋+1. 3) For any full binary ordered tree T, there exists a solution string w over an alphabet of size at most h+1, where h is the height of T. 4) For any complete binary ordered tree T with 2^k leaves, there exists a solution string w over an alphabet of size at most 4.

DOI： 10.1016/j.tcs.2018.06.044

記述言語：英語   掲載種別：研究論文（学術雑誌）  

The dictionary matching is a task to find all occurrences of pattern strings in a set D (called a dictionary) on a text string T. The Aho–Corasick-automaton (AC-automaton) which is built on D is a fundamental data structure which enables us to solve the dictionary matching problem in O(dlog⁡σ) preprocessing time and O(nlog⁡σ+occ) matching time, where d is the total length of the patterns in the dictionary D, n is the length of the text, σ is the alphabet size, and occ is the total number of occurrences of all the patterns in the text. The dynamic dictionary matching is a variant where patterns may dynamically be inserted into and deleted from the dictionary D. This problem is called semi-dynamic dictionary matching if only insertions are allowed. In this paper, we propose two efficient algorithms that can solve both problems with some modifications. For a pattern of length m, our first algorithm supports insertions in O(mlog⁡σ+log⁡d/log⁡log⁡d) time and pattern matching in O(nlog⁡σ+occ) for the semi-dynamic setting. This algorithm also supports both insertions and deletions in O(σm+log⁡d/log⁡log⁡d) time and pattern matching in O(n(log⁡d/log⁡log⁡d+log⁡σ)+occ(log⁡d/log⁡log⁡d)) time for the dynamic dictionary matching problem by some modifications. This algorithm is based on the directed acyclic word graph (DAWG) of Blumer et al. (JACM 1987). Our second algorithm, which is based on the AC-automaton, supports insertions in O(mlog⁡σ+u_f+u_o) time for the semi-dynamic setting and supports both insertions and deletions in O(σm+u_f+u_o) time for the dynamic setting, where u_f and u_o respectively denote the numbers of states in which the failure function and the output function need to be updated. This algorithm performs pattern matching in O(nlog⁡σ+occ) time for both settings. Our algorithm achieves optimal update time for AC-automaton based methods over constant-size alphabets, since any algorithm which explicitly maintains the AC-automaton requires Ω(m+u_f+u_o) update time.

DOI： 10.1016/j.tcs.2018.04.016

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1007/s00224-017-9794-5

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

We consider the problem of computing all maximal repetitions contained in a string that is given in run-length encoding. Given a run-length encoding of a string, we show that the maximum number of maximal repetitions contained in the string is at most m+k-1, where m is the size of the run-length encoding, and k is the number of run-length factors whose exponent is at least 2. We also show an algorithm for computing all maximal repetitions in O(m α (m)) time and O(m) space, where α denotes the inverse Ackermann function.

DOI： 10.4230/LIPIcs.ISAAC.2017.33

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1007/978-3-319-67428-5_5

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1587/transfun.E100.A.1785

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1137/15M1011032

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1007/978-3-319-67428-5_23

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1007/978-3-319-67428-5_26

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1007/s00224-017-9794-5

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.4230/LIPIcs.dMFCS.2017.10

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1007/978-3-319-51963-0_28

その他リンク： http://dx.doi.org/10.1007/978-3-319-51963-0_28

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1007/978-3-319-51963-0_29

その他リンク： http://dx.doi.org/10.1007/978-3-319-51963-0_29

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.tcs.2016.03.005

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.tcs.2016.02.017

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.dam.2016.04.009

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1007/978-3-319-44543-4_15

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1007/s00453-016-0178-z

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.4230/LIPIcs.MFCS.2016.38

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.4230/LIPIcs.MFCS.2016.69

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.4230/LIPIcs.MFCS.2016.72

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1007/978-3-319-44543-4_17

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.4230/LIPIcs.CPM.2016.27

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.4230/LIPIcs.CPM.2016.22

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.4230/LIPIcs.CPM.2016.1

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.4230/LIPIcs.STACS.2016.39

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

その他リンク： http://dx.doi.org/10.1007/978-3-662-49192-8_25

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

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

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

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

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1007/978-3-319-21500-6_6

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

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

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

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

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1007/978-3-319-18173-8_29

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.ic.2014.09.009

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1137/1.9781611973730.38

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

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

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

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

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.4230/LIPIcs.STACS.2014.675

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： dx.doi.org/10.1016/j.dam.2013.02.033

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1007/978-3-319-04298-5_44

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1007/978-3-319-02432-5_21

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1007/978-3-642-38905-4_16

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1007/978-3-642-38905-4_6

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1007/978-3-642-39274-0_28

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1007/978-3-642-40313-2_51

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： dx.doi.org/10.1016/j.tcs.2012.01.047

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： dx.doi.org/10.1007/978-3-642-35843-2_25

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： dx.doi.org/10.1016/j.jda.2012.07.006

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： dx.doi.org/10.1007/978-3-642-34109-0_10

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： dx.doi.org/10.1016/j.ipl.2012.06.017

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： dx.doi.org/10.1007/978-3-642-34109-0_38

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： dx.doi.org/10.1007/978-3-642-31265-6_18

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： dx.doi.org/10.1142/S0129054112400126

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： dx.doi.org/10.1142/S0129054112400126

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： dx.doi.org/10.1007/978-3-642-27660-6_25

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： dx.doi.org/10.1016/j.tcs.2011.09.008

掲載種別：研究論文（国際会議プロシーディングス）  

掲載種別：研究論文（学術雑誌）  

掲載種別：研究論文（学術雑誌）  

掲載種別：研究論文（国際会議プロシーディングス）  

掲載種別：研究論文（国際会議プロシーディングス）  

掲載種別：研究論文（学術雑誌）  

掲載種別：研究論文（学術雑誌）  

掲載種別：研究論文（国際会議プロシーディングス）  

掲載種別：研究論文（学術雑誌）  

掲載種別：研究論文（国際会議プロシーディングス）  

掲載種別：研究論文（国際会議プロシーディングス）  

掲載種別：研究論文（学術雑誌）  

掲載種別：研究論文（国際会議プロシーディングス）  

掲載種別：研究論文（国際会議プロシーディングス）  

掲載種別：研究論文（国際会議プロシーディングス）  

掲載種別：研究論文（国際会議プロシーディングス）  

掲載種別：研究論文（学術雑誌）  

掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

掲載種別：研究論文（学術雑誌）  

DOI： 10.1142/S0129054105003728

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/dam.2004.04.012

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.tcs.2004.07.008

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1142/S0129054105003728

掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1016/dam.2004.04.012

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

担当区分：責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： https://doi.org/10.1016/j.tcs.2023.114093

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：その他   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1007/978-3-031-33264-7_8

記述言語：その他   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：その他   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.ic.2022.104999

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Abstract

The similarity between a pair of time series, i.e., sequences of indexed values in time order, is often estimated by the dynamic time warping (DTW) distance, instead of any in the well-studied family of measures including the longest common subsequence (LCS) length and the edit distance. Although it may seem as if the DTW and the LCS(-like) measures are essentially different, we reveal that the DTW distance can be represented by the longest increasing subsequence (LIS) length of a sequence of integers, which is the LCS length between the integer sequence and itself sorted. For a given pair of time series of length n such that the dissimilarity between any elements is an integer between zero and c, we propose an integer sequence that represents any substring-substring DTW distance as its band-substring LIS length. The length of the produced integer sequence is $$O(c n^2)$$, which can be translated to $$O(n^2)$$ for constant dissimilarity functions. To demonstrate that techniques developed under the LCS(-like) measures are directly applicable to analysis of time series via our reduction of DTW to LIS, we present time-efficient algorithms for DTW-related problems utilizing the semi-local sequence comparison technique developed for LCS-related problems.

DOI： 10.1007/s00453-022-00968-2

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Given a string T of length n, a substring u=T[i..j] of T is called a shortest unique substring (SUS) for an interval [s,t] if (a) u occurs exactly once in T, (b) u contains the interval [s,t] (i.e. i≤s≤t≤j), and (c) every substring v of T with |v|<|u| containing [s,t] occurs at least twice in T. Given a query interval [s,t]⊂[1,n], the interval SUS problem is to output all the SUSs for the interval [s,t]. In this article, we propose a 4n+o(n) bits data structure answering an interval SUS query in output-sensitive O(occ) time, where occ is the number of returned SUSs. Additionally, we focus on the point SUS problem, which is the interval SUS problem for s=t. Here, we propose a ⌈(log₂⁡3+1)n⌉+o(n) bits data structure answering a point SUS query in the same output-sensitive time. We also propose space-efficient algorithms for computing the minimal unique substrings of T.

DOI： 10.1016/j.tcs.2020.09.017

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

Two strings x and y over of equal length are said to parameterized match (p-match) if there is a renaming bijection f : That is identity on and transforms x to y (or vice versa). The p-matching problem is to look for substrings in a text that p-match a given pattern. In this paper, we propose parameterized suffix automata (p-suffix automata) and parameterized directed acyclic word graphs (PDAWGs) which are the p-matching versions of suffix automata and DAWGs. While suffix automata and DAWGs are equivalent for standard strings, we show that p-suffix automata can have(n2) nodes and edges but PDAWGs have only O(n) nodes and edges, where n is the length of an input string. We also give O(n log( + ))-time O(n)-space algorithm that builds the PDAWG in a left-to-right online manner. As a byproduct, it is shown that the parameterized suffix tree for the reversed string can also be built in the same time and space, in a right-to-left online manner. 2012 ACM Subject Classification Theory of computation ! Pattern matching.

DOI： 10.4230/LIPIcs.CPM.2020.26

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

The equidistant subsequence pattern matching problem is considered. Given a pattern string P and a text string T, we say that P is an equidistant subsequence of T if P is a subsequence of the text such that consecutive symbols of P in the occurrence are equally spaced. We can consider the problem of equidistant subsequences as generalizations of (sub-)cadences. We give bit-parallel algorithms that yield o(n2) time algorithms for finding k-(sub-)cadences and equidistant subsequences. Furthermore, O(n log2 n) and O(n log n) time algorithms, respectively for equidistant and Abelian equidistant matching for the case P = 3, are shown. The algorithms make use of a technique that was recently introduced which can efficiently compute convolutions with linear constraints. 2012 ACM Subject Classification Mathematics of computing ! Combinatorial algorithms.

DOI： 10.4230/LIPIcs.CPM.2020.12

記述言語：英語   掲載種別：研究論文（学術雑誌）  

In this paper, we introduce new types of approximate palindromes called single-arm-gapped palindromes (shortly SAGPs). A SAGP contains a gap in either its left or right arm, which is in the form of either wgucu^Rw^R or wucu^Rgw^R, where w and u are non-empty strings, w^R and u^R are respectively the reversed strings of w and u, g is a string called a gap, and c is either a single character or the empty string. Here we call wu and u^Rw^R the arm of the SAGP, and |uv| the length of the arm. We classify SAGPs into two groups: those which have ucu^R as a maximal palindrome (type-1), and the others (type-2). We propose several algorithms to compute type-1 SAGPs with longest arms occurring in a given string, based on suffix arrays. Then, we propose a linear-time algorithm to compute all type-1 SAGPs with longest arms, based on suffix trees. Also, we show how to compute type-2 SAGPs with longest arms in linear time. We also perform some preliminary experiments to show practical performances of the proposed methods.

DOI： 10.1016/j.tcs.2019.10.025

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： https://doi.org/10.3390/a13040103

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

For a string S, a palindromic substring S[i.j] is said to be a shortest unique palindromic substring (SUPS) for an interval [s,t] in S, if S[i.j] occurs exactly once in S, the interval [i,j] contains [s,t], and every palindromic substring containing [s,t] which is shorter than S[i.j] occurs at least twice in S. In this paper, we study the problem of answering SUPS queries on run-length encoded strings. We show how to preprocess a given run-length encoded string RLE_S of size m in O(m) space and O(mlogσRLES+mlogm/loglogm) time so that all SUPSs for any subsequent query interval can be answered in O(logm/loglogm+α) time, where α is the number of outputs, and σRLES is the number of distinct runs of RLE_S. Additionaly, we consider a variant of the SUPS problem where a query interval is also given in a run-length encoded form. For this variant of the problem, we present two alternative algorithms with faster queries. The first one answers queries in O(loglogm/logloglogm+α) time and can be built in O(mlogσRLES+mlogm/loglogm) time, and the second one answers queries in O(log log m+ α) time and can be built in O(mlogσRLES) time. Both of these data structures require O(m) space.

DOI： 10.1007/s00224-020-09980-x

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.4230/LIPIcs.ISAAC.2019.40

記述言語：その他   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.tcs.2018.06.044

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

We prove that it is NP-complete to decide whether a given string can be factored into palindromes that are each unique in the factorization.

DOI： 10.1142/S0129054118400014

記述言語：英語   掲載種別：研究論文（学術雑誌）  

The 2-LCPS problem, first introduced by Chowdhury et al. (2014) [17], asks one to compute (the length of) a longest common palindromic subsequence between two given strings A and B. We show that the 2-LCPS problem is at least as hard as the well-studied longest common subsequence problem for four strings. Then, we present a new algorithm which solves the 2-LCPS problem in O (sigma M-2 + n) time, where n denotes the length of A and B, M denotes the number of matching positions between A and B, and a denotes the number of distinct characters occurring in both A and B. Our new algorithm is faster than Chowdhury et al.'s sparse algorithm when sigma = o(log(2) n log log n). (C) 2017 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.ipl.2017.08.006

記述言語：英語   掲載種別：研究論文（学術雑誌）  

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
An α-gapped repeat (α ≥ 1) in a word w is a factor uvu of w such that |uv| ≤ α|u|
the two occurrences of u are called arms of this α-gapped repeat. An α-gapped repeat is called maximal if its arms cannot be extended simultaneously with the same character to the right nor to the left. We show that the number of all maximal α-gapped repeats occurring in words of length n is upper bounded by 18αn. In the case of α-gapped palindromes, i.e., factors uvu⊺ with |uv|≤ α|u|, we show that the number of all maximal α-gapped palindromes occurring in words of length n is upper bounded by 28αn + 7n. Both upper bounds allow us to construct algorithms finding all maximal α-gapped repeats and/or all maximal α-gapped palindromes of a word of length n on an integer alphabet of size nO ( 1 ) in O(αn) time. The presented running times are optimal since there are words that have Θ(αn) maximal α-gapped repeats/palindromes.

DOI： 10.1007/s00224-017-9794-5

記述言語：英語   掲載種別：研究論文（学術雑誌）  

This paper considers enumeration of substring equivalence classes introduced by Blumer et al. (J ACM 34(3):578-595, 1987). These equivalence classes were originally proposed to define a text indexing structure called compact directed acyclic word graphs (CDAWGs). These equivalence classes are also useful for text analysis, since they group together redundant substrings with essentially identical occurrences. In this paper, we present how to enumerate these equivalence classes using only suffix arrays and two auxiliary arrays (rank arrays and lcp arrays), in O(n) time for a given string of length n over the integer alphabet. The proposed method overcomes all the existing algorithms which require time O(n log sigma), where sigma is the alphabet size. Our experimental results show that the proposed method is also practically faster and more memory efficient than the existing ones. Furthermore, we propose an O(n)-time algorithm which constructs the CDAWG of an input string over the integer alphabet. This algorithm is based on the above-mentioned algorithm to enumerate equivalence classes. Our experiments show that the proposed method runs faster than the existing algorithm on large alphabets.

DOI： 10.1007/s00453-016-0178-z

記述言語：英語   掲載種別：研究論文（学術雑誌）  

We present a new data structure called the packed compact trie (packed c-trie) which stores a set S of k strings of total length n in n log + O(k log n) bits of space and supports fast pattern matching queries and updates, where is the alphabet size. Assume that = log n letters are packed in a single machine word on the standard word RAM model, and let f (k
n) denote the query and update times of the dynamic predecessor/successor data structure of our choice which stores k integers from universe [1
n] in O(k log n) bits of space. Then, given a string of length m, our packed c-tries support pattern matching queries and insert/delete operations in O( m f (k
n)) worst-case time and in O( m + f (k
n)) expected time. Our experiments show that our packed c-tries are faster than the standard compact tries (a.k.a. Patricia trees) on real data sets. We also discuss applications of our packed c-tries.

DOI： 10.1587/transfun.E100.A.1785

記述言語：英語   掲載種別：研究論文（学術雑誌）  

The Lyndon factorization of a string w is a unique factorization l(1)(p1),..., l(m)(pm) of w such that l(1),..., l(m) is a sequence of Lyndon words that is monotonically decreasing in lexicographic order. In this paper, we consider the reverse-engineering problem on Lyndon factorization: Given a sequence S = ((s(1), p(1)) (s(m), p(m))) of ordered pairs of positive integers, find a string w whose Lyndon factorization corresponds to the input sequence S, i.e., the Lyndon factorization of w is in a form of l(1)(p1),..., l(m)(pm) with vertical bar l(i)vertical bar = s(i) for all 1 <= i <= m. Firstly, we show that there exists a simple O(n)-time algorithm if the size of the alphabet is unbounded, where n is the length of the output string. Secondly, we present an O(n)-time algorithm to compute a string over an alphabet of the smallest size. Thirdly, we show how to compute only the size of the smallest alphabet in O(m) time. Fourthly, we give an O(m)-time algorithm to compute an O(m)-size representation of a string over an alphabet of the smallest size. Finally, we propose an efficient algorithm to enumerate all strings whose Lyndon factorizations correspond to S. (C) 2017 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2017.05.038

記述言語：英語   掲載種別：研究論文（学術雑誌）  

We present two efficient algorithms which, given a compressed representation of a string w of length N, compute the Lyndon factorization of w. Given a straight line program (SLP) S of size n that describes w, the first algorithm runs in O (n(2) + P (n, N) Q (n, N)n logn) time and O (n(2) + S(n, N)) space, where P(n, N), S(n, N), Q(n, N) are respectively the preprocessing time, space, and query time of a data structure for longest common extensions (LCE) on SLPs. Given the Lempel-Ziv 78 encoding of size s for w, the second algorithm runs in O (s logs) time and space. (C) 2016 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2016.03.005

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Let approximate to be a substring consistent equivalence relation (SCER) on strings such that for any two strings x, y, x approximate to y implies that (1) vertical bar x vertical bar = vertical bar y vertical bar and (2) x[i..j] approximate to y[i..j] for all 0 <= i <= j < vertical bar x vertical bar. Examples of SCER are parameterized pattern matching and order-preserving pattern matching. We present a generalized and efficient algorithm for pattern matching with SCER approximate to. Also, we show analogues of Fine and Wilt's periodicity lemma hold for SCER. (C) 2016 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2016.02.017

記述言語：英語   掲載種別：研究論文（学術雑誌）  

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 (2011) as objects of combinatorial interest in the study of Trapezoidal and Sturmian words. In this paper we present algorithms for computing closed factors (substrings) in strings. First, we consider the problem of 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, where n is the length of the string. This also leads to an algorithm to compute the maximal closed factor containing (i.e. covering) each position in the string in O(n log n/log log n) time. We also present linear time algorithms to factorize a string into a sequence of shortest closed factors of length at least two, to compute the shortest closed factor of length at least two starting at each position of the string, and to compute a minimal closed factor of length at least two containing each position of the string. (C) 2016 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2016.04.009

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

Given a string S of n symbols, a longest common extension query LCE(i, j) asks for the length of the longest common prefix of the ith and jth suffixes of S. LCE queries have several important applications in string processing, perhaps most notably to suffix sorting. Recently, Bille et al. (J. Discrete Algorithms 25:42-50, 2014, Proc. CPM 2015:65-76) described several data structures for answering LCE queries that offers a trade-off between data structure size and query time. In particular, for a parameter 1 ≤ τ ≤ n, their best deterministic solution is a data structure of size O(n/τ) which allows LCE queries to be answered in O(τ) time. However, the construction time for all deterministic versions of their data structure is quadratic in n. In this paper, we propose a deterministic solution that achieves a similar space-time trade-off of O(τ min{log τ, log n/τ}) query time using O(n/τ) space, but we significantly improve the construction time to O(nτ).

DOI： 10.4230/LIPIcs.CPM.2016.1

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

For α ≥ 1, an α-gapped repeat in a word w is a factor uvu of w such that |uv| ≤ α|u|
the two occurrences of a factor u in such a repeat are called arms. Such a repeat is called maximal if its arms cannot be extended simultaneously with the same symbol to the right nor to the left. We show that the number of all maximal α-gapped repeats occurring in words of length n is upper bounded by 18αn, allowing us to construct an algorithm finding all maximal α-gapped repeats of a word on an integer alphabet of size nO(1)
in O(αn) time. This result is optimal as there are words that have Θ(αn) maximal α-gapped repeats. Our techniques can be extended to get comparable results in the case of α-gapped palindromes, i.e., factors uvuT with |uv| ≤ α|u|.

DOI： 10.4230/LIPIcs.STACS.2016.39

記述言語：英語   掲載種別：研究論文（学術雑誌）  

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

記述言語：英語   掲載種別：研究論文（学術雑誌）  

We discuss the problem of edit distance computation under a dynamic setting, where one of the two compared strings may be modified by single-character edit operations and we wish to keep the edit distance information between the strings up-to-date. A previous algorithm by Kim and Park (2004) [6] solves a more limited problem where modifications can be done only at the ends of the strings (so-called decremental or incremental edits) and the edit operations have (essentially) unit costs. If the lengths of the two strings are m and n, their algorithm requires O(m+n) time per modification. We propose a simple and practical algorithm that (1) allows arbitrary non-negative costs for the edit operations and (2) allows the modifications to be done at arbitrary positions. If the latter string is modified at position &lt
sup&gt
j∗&lt
/sup&gt
, our algorithm requires O(min {rc(m+n),mn}) time, where r=min {&lt
sup&gt
j∗&lt
/sup&gt
,n-&lt
sup&gt
j∗&lt
/sup&gt
+1} and c is the maximum edit operation cost. This equals O(m+n) in the simple decremental/incremental unit cost case. Our experiments indicate that the algorithm performs much faster than the theoretical worst-case time limit O(mn) in the general case with arbitrary edit costs and modification positions. The main practical limitation of the algorithm is its Θ(mn) memory requirement for storing the edit distance information.

DOI： 10.1016/j.jda.2015.05.007

記述言語：英語   掲載種別：研究論文（学術雑誌）  

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 in patterns of total length N, we present an O (n(2) log 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 (n(3) logn log N) time and O (n(2) log N) space. In a spacial case where 7, 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 (n(3) logn log N) time with O (n(2) log N) working space. (C) 2015 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2015.01.019

記述言語：英語   掲載種別：研究論文（学術雑誌）  

We address the problems of detecting and counting various forms of regularities in a string represented as a straight-line program (SLP) which is essentially a context free grammar in the Chomsky normal form. Given an SLP of size n that represents a string s of length N, our algorithm computes all runs and squares in sin O(n(3)h) time and O(n(2)) space, where his the height of the derivation tree of the SLP. We also show an algorithm to compute all gapped-palindromes in O(n(3)h + gnh logN) time and O(n(2)) space, where g is the length of the gap. As one of the main components of the above solution, we propose a new technique called approximate doubling which seems to be a useful tool for a wide range of algorithms on SLPs. Indeed, we show that the technique can be used to compute the periods and covers of the string in O(n(2)h) time and O(nh(n + log(2)N)) time, respectively. (C) 2014 Elsevier Inc. All rights reserved.

DOI： 10.1016/j.ic.2014.09.009

記述言語：英語   掲載種別：研究論文（学術雑誌）  

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. (C) 2013 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2013.02.033

記述言語：英語   掲載種別：研究論文（学術雑誌）  

A palindrome is a string that reads the same forward and backward. For a string x, let Pals(x) be the set of all maximal palindromes of x, where each maximal palindrome in Pals(x) is encoded by a pair (c, r) of its center c and its radius r. Given a text t of length n and a pattern p of length m, the palindrome pattern matching problem is to compute all positions i oft such that Pals(p) = Pals(t[i : i + m - 1]). We present linear-time algorithms to solve this problem. (C) 2012 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2012.01.047

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

We present simple and efficient algorithms for calculating q-gram frequencies on strings represented in compressed form, namely, as a straight line program (SLP). Given an SLP of size n that represents string T, we present an O(qn) time and space algorithm that computes the occurrence frequencies of all q-grams in T. Computational experiments show that our algorithm and its variation are practical for small q, actually running faster on various real string data, compared to algorithms that work on the uncompressed text. We also discuss applications in data mining and classification of string data, for which our algorithms can be useful. © 2012 Elsevier B.V.

DOI： 10.1016/j.jda.2012.07.006

記述言語：英語   掲載種別：研究論文（学術雑誌）  

We give a simple algorithm that, given a straight-line program of size n for a string S of length N, tests whether S is square-free in O(n(4) log N) time and O(n(2)) space. The algorithm also allows us to test square-freeness on an arbitrary composition system of size c for S. in O(c(4) log(5) N) time and O(c(2) log(2) N) space, which is faster than using the algorithm by Gasieniec, Karpinski, Plandowski, and Rytter (1996) [4]. (C) 2012 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.ipl.2012.06.017

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Text mining from large scaled data is of great importance in computer science. In this paper, we consider fundamental problems on text mining from compressed strings, i.e., computing a longest repeating substring, longest non-overlapping repeating substring, most frequent substring, and most frequent non-overlapping substring from a given compressed string. Also, we tackle the following novel problem: given a compressed text and compressed pattern, compute the representative of the equivalence class of the pattern w.r.t. the text. We present algorithms that solve the above problems in time polynomial in the size of input compressed strings. The compression scheme we consider is straight line program (SLP) which has exponential compression, and therefore our algorithms are more efficient than any existing algorithms that require decompression of given SLPs.

DOI： 10.1142/S0129054112400126

記述言語：英語   掲載種別：研究論文（学術雑誌）  

The parameterized pattern matching problem is to check if there exists a renaming bijection on the alphabet with which a given pattern can be transformed into a substring of a given text. A parameterized border array (p-border array) is a parameterized version of a standard border array, and we can efficiently solve the parameterized pattern matching problem using p-border arrays.
In this paper, we present a linear time algorithm to verify if a given integer array is a valid p-border array for a binary alphabet. We also show a linear time algorithm to compute all binary parameterized strings sharing a given p-border array. In addition, we give an algorithm which computes all p-border arrays of length at most n, where n is a given threshold. This algorithm runs in O(B-2(n)) time, where B-2(n) is the number of all p-border arrays of length n for a binary parameter alphabet.
The problems with a larger alphabet are much more difficult. Still, we present an O(n(1.5)) - time O(n) - space algorithm to verify if a given integer array of length n is a valid p-border array for an unbounded alphabet. The best previously known solution to this task takes time proportional to the n-th Bell number 1/e Sigma(infinity)(k=0) k(n)/k(l), and hence our algorithm is much more efficient. Also, we show that it is possible to enumerate all p-border arrays of length at most n for an unbounded alphabet in O(B(n)n(2.5)) time, where B-n denotes the number of p-border arrays of length n. (C) 2011 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2011.09.008

掲載種別：研究論文（国際会議プロシーディングス）  

掲載種別：研究論文（国際会議プロシーディングス）  

掲載種別：研究論文（国際会議プロシーディングス）  

掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

In this paper, we study the missing patterns problem: Find the shortest pair of patterns that do not occur close to each other in a given text, i.e., the distance between their occurrences is always greater than a given threshold α. We present various solutions to this problem, as well as to the case where the patterns in the pair are required to be of the same length. This work is motivated by optimizing the sensitivity of PCR. Experiments show that our algorithm is practical enough to handle human genome data. © 2010 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.jda.2010.08.005

掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

We consider grammar-based text compression with longest first substitution (LFS), where non-overlapping occurrences of a longest repeating factor of the input text are replaced by a new non-terminal symbol. We present the first linear-time algorithm for LFS. Our algorithm employs a new data structure called sparse lazy suffix trees. We also deal with a more sophisticated version of LFS, called LFS2, that allows better compression. The first linear-time algorithm for LFS2 is also presented.

DOI： 10.3390/a2041429

掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

This paper studies two problems on compressed strings described in terms of straight line programs (SLPs). One is to compute the length of the longest common substring of two given SLP-compressed strings, and the other is to compute all palindromes of a given SLP-compressed string. In order to solve these problems efficiently (in polynomial time w.r.t. the compressed size) decompression is never feasible, since the decompressed size can be exponentially large. We develop combinatorial algorithms that solve these problems in O(n(4) log n) time with O(n(3)) space, and in O(n(4)) time with O(n(2)) space, respectively, where n is the size of the input SLP-compressed strings. (C) 2008 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2008.12.016

掲載種別：研究論文（国際会議プロシーディングス）  

掲載種別：研究論文（国際会議プロシーディングス）  

掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

We analyze the complexity of graph reachability queries on ST-graphs, defined as directed acyclic graphs (DAGs) obtained by merging the suffix tree of a given string and its suffix links. Using a simplified reachability labeling algorithm presented by Agrawal et al. (1989), we show that for a random string of length n, its ST-graph can be preprocessed in O(n log n) expected time and space to answer reachability queries in O(log n) time. Furthermore, we present a series of strings that require circle minus(n root n) time and space to answer reachability queries in O(log n) time for the same algorithm. Exhaustive computational calculations for strings of length n <= 33 have revealed that the same strings are also the worst case instances of the algorithm. We therefore conjecture that reachability queries can be answered in O(log n) time with a worst case time and space preprocessing complexity of circle minus(n root n).

DOI： 10.1142/S0129054108005590

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

We study the fully compressed pattern matching problem (FCPM problem): Given T and P which are descriptions of text T and pattern P respectively, find the occurrences of P in T without decompressing T or P. This problem is rather challenging since patterns am also given in a compressed form. In this paper we present an FCPM algorithm for simple collage systems. Collage systems are a general framework representing various kinds of dictionary-based compressions in a uniform way, and simple collage systems are a subclass that includes LZW and LZ78 compressions. Collage systems are of the form < D, S >, where D is a dictionary and S is a sequence of variables from 1). Our F(;PM algorithm performs in O(parallel to D parallel to(2) + mn log |S|) time, where n = |T| = parallel to D parallel to + |S| and m = |P|. This is faster than the previous best result of O(m(2)n(2)) time.

DOI： 10.1142/S0129054105003728

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Many different index structures, providing efficient solutions to problems related to pattern matching, have been introduced so far. Examples of these structures are suffix trees and directed acyclic word graphs (DAWGs), which can be efficiently constructed in linear time and space. Compact directed acyclic word graphs (CDAWGs) are an index structure preserving some features of both suffix trees and DAWGs, and require less space than both of them. An algorithm which directly constructs CDAWGs in linear time and space was first introduced by Crochemore and Verin, based on McCreight's algorithm for constructing suffix trees. In this work, we present a novel on-line linear-time algorithm that builds the CDAWG for a single string as well as for a set of strings, inspired by Ukkonen's on-line algorithm for constructing suffix trees. (C) 2004 Elsevier B.V. All rights reserved.

DOI： 10.1016/dam.2004.04.012

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Given a set S of strings, a DFA accepting S offers a very time-efficient solution to the pattern matching problem over S. The key is how to implement such a DFA in the trade-off between time and space, and especially the choice of how to implement the transitions of each state is critical. Bentley and Sedgewick proposed an effective tree structure called ternary trees. The idea of ternary trees is to 'implant' the process of binary search for transitions into the structure of the trees themselves. This way the process of binary search becomes visible, and the implementation of the trees becomes quite easy. The directed acyclic word graph (DAWG) of a string w is the smallest DFA that accepts all suffixes of w, and requires only linear space. We apply the scheme of ternary trees to DAWGs, introducing a new data structure named ternary DAWGs (TDAWGs). Furthermore, the scheme of AVL trees is applied to the TDAWGs, yielding a more time-efficient structure AVL TDAWGs. We also perform some experiments that show the efficiency of TDAWGs and AVL TDAWGs, compared to DAWGs in which transitions are implemented by linked lists. (C) 2004 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2004.07.008

掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

We present an efficient algorithm for detecting putative regulatory elements in the upstream DNA sequences of genes, using gene expression information obtained from microarray experiments. Based on a generalized suffix tree, our algorithm looks for motif patterns whose appearance in the upstream region is most correlated with the expression levels of the genes. We are able to find the optimal pattern, in time linear in the total length of the upstream sequences. We implement and apply our algorithm to publicly available microarray gene expression data, and show that our method is able to discover biologically significant motifs, including various motifs which have been reported previously using the same data set. We further discuss applications for which the efficiency of the method is essential, as well as possible extensions to our algorithm. © Imperial College Press.

DOI： 10.1142/S0219720004000612

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Suffix trees are a well-known and widely-studied data structure highly useful for string matching. The suffix tree of a string ω can be constructed in O(n) time and space, where n denotes the length of ω. Larsson achieved an efficient algorithm to maintain suffix trees for a sliding window. It contributes to prediction by partial matching (PPM) style statistical data compression scheme. Compact directed acyclic word graphs (CDAWGs) are a more space-economical data structure for indexing strings. In this paper we propose a linear-time algorithm to maintain CDAWGs for a sliding window. © 2003 Elsevier B.V. All rights reserved.

DOI： 10.1016/S1570-8667(03)00064-9

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

開催年月日： 2018年8月

記述言語：英語   会議種別：口頭発表（一般）  

国名：日本国  

開催年月日： 2018年7月

記述言語：英語  

開催地：Qingdao   国名：中華人民共和国  

The longest Lyndon substring of a string T is the longest substring of T which is a Lyndon word. LLS(T) denotes the length of the longest Lyndon substring of a string T. In this paper, we consider computing LLS(T′) where T′ is an edited string formed from T. After O(n) time and space preprocessing, our algorithm returns LLS(T′) in O(log n) time for any single character edit. We also consider a version of the problem with block edits, i.e., a substring of T is replaced by a given string of length l. After O(n) time and space preprocessing, our algorithm returns LLS(T′) in O(l log σ + log n) time for any block edit where σ is the number of distinct characters in T. We can modify our algorithm so as to output all the longest Lyndon substrings of T′ for both problems.

開催年月日： 2018年7月

記述言語：英語  

開催地：Qingdao   国名：中華人民共和国  

We revisit the problem of computing the Lyndon factorization of a string w of length N which is given as a straight line program (SLP) of size n. For this problem, we show a new algorithm which runs in O(P(n,N) + Q(n,N)n log logN) time and O(n logN + S(n,N)) space where P(n,N), S(n,N), Q(n,N) are respectively the pre-processing time, space, and query time of a data structure for longest common extensions (LCE) on SLPs. Our algorithm improves the algorithm proposed by I et al. (TCS '17), and can be more efficient than the O(N)-time solution by Duval (J. Algorithms '83) when w is highly compressible.

開催年月日： 2018年7月

記述言語：英語  

開催地：Qingdao   国名：中華人民共和国  

It is known that the length of the longest substring palindromes (LSPals) of a given string T of length n can be computed in O(n) time by Manacher's algorithm [J. ACM '75]. In this paper, we consider the problem of finding the LSPal after the string is edited. We present an algorithm that uses O(n) time and space for preprocessing, and answers the length of the LSPals in O(log(min{ω, log n})) time after single character substitution, insertion, or deletion, where ω denotes the number of distinct characters appearing in T. We also propose an algorithm that uses O(n) time and space for preprocessing, and answers the length of the LSPals in O(ℓ+log n) time, after an existing substring in T is replaced by a string of arbitrary length ℓ.

開催年月日： 2017年12月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Phuket   国名：タイ王国  

開催年月日： 2017年9月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Palermo   国名：イタリア共和国  

開催年月日： 2017年9月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Palermo   国名：イタリア共和国  

開催年月日： 2017年9月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Palermo   国名：イタリア共和国  

開催年月日： 2017年8月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Prague   国名：チェコ共和国  

開催年月日： 2017年8月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Aalborg   国名：デンマーク王国  

開催年月日： 2017年7月

記述言語：英語  

開催地：Newcastle, NSW   国名：オーストラリア連邦  

Two strings x and y are said to be Abelian equivalent if x is a permutation of y, or vice versa. If a string z satisfies z = xy with x and y being Abelian equivalent, then z is said to be an Abelian square. If a string w can be factorized into a sequence v₁, …, vs of strings such that v₁, …, v_s-1 are all Abelian equivalent and vs is a substring of a permutation of v₁, then w is said to have a regular Abelian period (p, t) where p = |v1| and t = |v_s|. If a substring w1[i.i+l-1] of a string w1 and a substring w2[j.j + l - 1] of another string w2 are Abelian equivalent, then the substrings are said to be a common Abelian factor of w1 and w2 and if the length l is the maximum of such then the substrings are said to be a longest common Abelian factor of w1 and w2. We propose efficient algorithms which compute these Abelian regularities using the run length encoding (RLE) of strings. For a given string w of length n whose RLE is of size m, we propose algorithms which compute all Abelian squares occurring in w in O(mn) time, and all regular Abelian periods of w in O(mn) time. For two given strings w1 and w2 of total length n and of total RLE size m, we propose an algorithm which computes all longest common Abelian factors in O(m²n) time.

開催年月日： 2017年7月

記述言語：英語  

開催地：Newcastle, NSW   国名：オーストラリア連邦  

palindrome is a string that reads the same forward and backward. A palindromic substring P of a string S is called a shortest unique palindromic substring (SUPS) for an interval [s, t] in S, if P occurs exactly once in S, this occurrence of P contains interval [s, t], and every palindromic substring of S which contains interval [s, t] and is shorter than P occurs at least twice in S. The SUPS problem is, given a string S, to preprocess S so that for any subsequent query interval [s, t] all the SUPSs for interval [s, t] can be answered quickly. We present an optimal solution to this problem. Namely, we show how to preprocess a given string S of length n in O(n) time and space so that all SUPSs for any subsequent query interval can be answered in O(α + 1) time, where α is the number of outputs.

開催年月日： 2017年7月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Newcastle   国名：オーストラリア連邦  

開催年月日： 2017年7月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Newcastle   国名：オーストラリア連邦  

開催年月日： 2017年7月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Warsaw   国名：ポーランド共和国  

開催年月日： 2017年7月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Warsaw   国名：ポーランド共和国  

開催年月日： 2017年7月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Warsaw   国名：ポーランド共和国  

開催年月日： 2016年8月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Krakow   国名：ポーランド共和国  

開催年月日： 2016年8月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Helsinki   国名：フィンランド共和国  

開催年月日： 2016年8月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Prague   国名：チェコ共和国  

開催年月日： 2016年8月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Prague   国名：チェコ共和国  

開催年月日： 2016年8月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Krakow   国名：ポーランド共和国  

開催年月日： 2016年6月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Tel Aviv   国名：イスラエル国  

開催年月日： 2016年6月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Tel Aviv   国名：イスラエル国  

開催年月日： 2016年6月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Tel Aviv   国名：イスラエル国  

開催年月日： 2016年1月 - 2017年1月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Limerick   国名：アイルランド  

開催年月日： 2016年1月 - 2017年1月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Limerick   国名：アイルランド  

開催年月日： 2016年1月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Harrachov   国名：チェコ共和国  

開催年月日： 2015年12月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Nagoya   国名：日本国  

開催年月日： 2015年9月 - 2016年8月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Helsinki   国名：フィンランド共和国  

開催年月日： 2015年9月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：London   国名：グレートブリテン・北アイルランド連合王国(英国)  

開催年月日： 2015年9月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：London   国名：グレートブリテン・北アイルランド連合王国(英国)  

開催年月日： 2015年8月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Prague   国名：チェコ共和国  

開催年月日： 2015年8月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Prague   国名：チェコ共和国  

開催年月日： 2015年7月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Liverpool   国名：グレートブリテン・北アイルランド連合王国(英国)  

開催年月日： 2015年6月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Ischia Island   国名：イタリア共和国  

開催年月日： 2015年6月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Ischia Island   国名：イタリア共和国  

開催年月日： 2015年5月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Paris   国名：フランス共和国  

開催年月日： 2015年1月

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：京都   国名：日本国  

開催年月日： 2015年1月

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：京都   国名：日本国  

開催年月日： 2015年1月

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：京都   国名：日本国  

開催年月日： 2015年1月

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：京都   国名：日本国  

開催年月日： 2015年1月

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：京都   国名：日本国  

開催年月日： 2015年1月

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：京都   国名：日本国  

開催年月日： 2015年1月

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：京都   国名：日本国  

開催年月日： 2015年1月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：San Diego   国名：アメリカ合衆国  

開催年月日： 2014年9月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Prague   国名：チェコ共和国  

開催年月日： 2014年9月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Prague   国名：チェコ共和国  

開催年月日： 2014年8月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Budapest   国名：ハンガリー共和国  

開催年月日： 2014年6月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Moscow   国名：ロシア連邦  

開催年月日： 2014年3月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Lyon   国名：フランス共和国  

開催年月日： 2014年1月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Harrachov   国名：チェコ共和国  

開催年月日： 2013年10月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Jerusalem   国名：イスラエル国  

開催年月日： 2013年8月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Klosterneuburg   国名：オーストリア共和国  

開催年月日： 2013年8月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Prague   国名：チェコ共和国  

開催年月日： 2013年7月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Halifax   国名：カナダ  

開催年月日： 2013年6月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Bad Herrenalb   国名：ドイツ連邦共和国  

開催年月日： 2013年6月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Bad Herrenalb   国名：ドイツ連邦共和国  

開催年月日： 2013年3月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Snowbird   国名：アメリカ合衆国  

開催年月日： 2013年3月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Snowbird   国名：アメリカ合衆国  

開催年月日： 2013年1月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Špindlerův Mlýn   国名：チェコ共和国  

開催年月日： 2012年10月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Cartagena de Indias   国名：コロンビア共和国  

開催年月日： 2012年10月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Cartagena de Indias   国名：コロンビア共和国  

開催年月日： 2012年10月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Cartagena de Indias   国名：コロンビア共和国  

開催年月日： 2012年7月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Helsinki   国名：フィンランド共和国  

開催年月日： 2012年1月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Špindlerův Mlýn   国名：チェコ共和国  

開催年月日： 2011年10月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Pisa   国名：イタリア共和国  

開催年月日： 2011年8月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Prague   国名：チェコ共和国  

開催年月日： 2011年8月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Prague   国名：チェコ共和国  

開催年月日： 2011年6月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Palermo   国名：イタリア共和国  

開催年月日： 2011年6月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Palermo   国名：イタリア共和国  

開催年月日： 2011年1月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Perth   国名：オーストラリア連邦  

開催年月日： 2010年10月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Los Cabos   国名：メキシコ合衆国  

開催年月日： 2010年9月

会議種別：口頭発表（一般）  

国名：日本国  

開催年月日： 2010年9月

会議種別：口頭発表（一般）  

国名：日本国  

開催年月日： 2010年7月

会議種別：口頭発表（一般）  

国名：日本国  

開催年月日： 2010年6月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：New York   国名：アメリカ合衆国  

開催年月日： 2009年7月

会議種別：口頭発表（一般）  

国名：日本国  

開催年月日： 2009年3月

会議種別：口頭発表（一般）  

国名：日本国  

開催年月日： 2009年1月

会議種別：口頭発表（一般）  

国名：日本国  

開催年月日： 2008年10月

会議種別：口頭発表（一般）  

国名：日本国  

開催年月日： 2008年3月

会議種別：口頭発表（一般）  

国名：日本国  

開催年月日： 2008年1月

会議種別：口頭発表（一般）  

国名：日本国  

開催年月日： 2007年10月

会議種別：口頭発表（一般）  

国名：日本国  

開催年月日： 2007年3月

会議種別：口頭発表（一般）  

国名：日本国  

開催年月日： 2005年11月

会議種別：口頭発表（一般）  

国名：日本国  

開催年月日： 2005年9月

会議種別：口頭発表（一般）  

開催地：東北大学   国名：日本国  

開催年月日： 2003年3月

会議種別：口頭発表（一般）  

開催地：九州大学 国際ホール   国名：日本国  

開催年月日： 2001年7月

会議種別：口頭発表（一般）  

国名：日本国  

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：京都府   国名：日本国  

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：京都府   国名：日本国  

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：京都府   国名：日本国  

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：京都府   国名：日本国  

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：京都府   国名：日本国  

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：京都府   国名：日本国  

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：京都府   国名：日本国  

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：京都府   国名：日本国  

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：京都府   国名：日本国  

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：京都府   国名：日本国  

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：山口県   国名：日本国  

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：福岡市   国名：日本国  

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：京都府   国名：日本国  

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：京都府   国名：日本国  

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：京都府   国名：日本国  

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：京都府   国名：日本国  

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：京都府   国名：日本国  

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：山口県   国名：日本国  

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：山口県   国名：日本国  

記述言語：英語   会議種別：口頭発表（一般）  

国名：フランス共和国  

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Online   国名：その他  

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Online   国名：その他  

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Online   国名：その他  

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Online   国名：その他  

開催年月日： 2023年8月 - 2023年6月

記述言語：英語  

開催地：Prague   国名：チェコ共和国  

開催年月日： 2023年6月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Umeå   国名：スウェーデン王国  

開催年月日： 2023年6月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Umeå   国名：スウェーデン王国  

開催年月日： 2023年1月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Nový Smokovec   国名：スロバキア共和国  

開催年月日： 2022年6月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Prague   国名：チェコ共和国  

開催年月日： 2022年6月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Prague   国名：チェコ共和国  

開催年月日： 2022年6月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Prague   国名：チェコ共和国  

開催年月日： 2020年6月

記述言語：英語  

開催地：Copenhagen (online)   国名：デンマーク王国  

開催年月日： 2020年6月

記述言語：英語  

開催地：Copenhagen (online)   国名：デンマーク王国  

開催年月日： 2020年1月

記述言語：英語  

開催地：Limassol   国名：キプロス共和国  

The longest common subsequence (LCS) problem is a central problem in stringology that finds the longest common subsequence of given two strings A and B. More recently, a set of four constrained LCS problems (called generalized constrained LCS problem) were proposed by Chen and Chao [J. Comb. Optim, 2011]. In this paper, we consider the substring-excluding constrained LCS (STR-EC-LCS) problem. A string Z is said to be an STR-EC-LCS of two given strings A and B excluding P if, Z is one of the longest common subsequences of A and B that does not contain P as a substring. Wang et al. proposed a dynamic programming solution which computes an STR-EC-LCS in O(mnr) time and space where [Inf. Process. Lett., 2013]. In this paper, we show a new solution for the STR-EC-LCS problem. Our algorithm computes an STR-EC-LCS in time where denotes the set of distinct characters occurring in both A and B, and L is the length of the STR-EC-LCS. This algorithm is faster than the O(mnr)-time algorithm for short/long STR-EC-LCS (namely, or), and is at least as efficient as the O(mnr)-time algorithm for all cases.

開催年月日： 2020年1月

記述言語：英語  

開催地：Limassol   国名：キプロス共和国  

A substring u of a string T is called a minimal unique substring (MUS) of T if u occurs exactly once in T and any proper substring of u occurs at least twice in T. A string w is called a minimal absent word (MAW) of T if w does not occur in T and any proper substring of w occurs in T. In this paper, we study the problems of computing MUSs and MAWs in a sliding window over a given string T. We first show how the set of MUSs can change in a sliding window over T, and present an-time and O(d)-space algorithm to compute MUSs in a sliding window of width d over T, where is the maximum number of distinct characters in every window. We then give tight upper and lower bounds on the maximum number of changes in the set of MAWs in a sliding window over T. Our bounds improve on the previous results in Crochemore et al. (2017).

開催年月日： 2019年12月

記述言語：英語  

開催地：Shanghai   国名：中華人民共和国  

For a set D of documents and a positive integer d, a string w is said to be d-left-right maximal, if (1) w occurs in at least d documents in D, and (2) any proper superstring of w occurs in less than d documents. The left-right-maximal generic words problem is, given a set D of documents, to preprocess D so that for any string p and for any positive integer d, all the superstrings of p that are d-left-right maximal can be answered quickly. In this paper, we present an O(n log m) space data structure (in words) which answers queries in O(|p| + o log log m) time, where n is the total length of documents in D, m is the number of documents in D and o is the number of outputs. Our solution improves the previous one by Nishimoto et al. (PSC 2015), which uses an O(n log n) space data structure answering queries in O(|p| + r · log n + o · log² n) time, where r is the number of right-extensions q of p occurring in at least d documents such that any proper right extension of q occurs in less than d documents.

開催年月日： 2019年10月

記述言語：英語  

開催地：Segovia   国名：スペイン  

Given a string T of length n, a substring of T is called a shortest unique substring (SUS) for an interval [s, t] if (a) u occurs exactly once in T, (b) u contains the interval [s, t] (i.e.), and (c) every substring v of T with containing [s, t] occurs at least twice in T. Given a query interval, the interval SUS problem is to output all the SUSs for the interval [s, t]. In this article, we propose a bits data structure answering an interval SUS query in output-sensitive time, where is the number of returned SUSs. Additionally, we focus on the point SUS problem, which is the interval SUS problem for. Here, we propose a bits data structure answering a point SUS query in the same output-sensitive time.

開催年月日： 2019年10月

記述言語：英語  

開催地：Segovia   国名：スペイン  

We revisit the problem of longest common property preserving substring queries introduced by Ayad et al. (SPIRE 2018, arXiv 2018). We consider a generalized and unified on-line setting, where we are given a set X of k strings of total length n that can be pre-processed so that, given a query string y and a positive integer (Formula presented), we can determine the longest substring of y that satisfies some specific property and is common to at least (Formula presented) strings in X. Ayad et al. considered the longest square-free substring in an on-line setting and the longest periodic and palindromic substring in an off-line setting. In this paper, we give efficient solutions in the on-line setting for finding the longest common square, periodic, palindromic, and Lyndon substrings. More precisely, we show that X can be pre-processed in O(n) time resulting in a data structure of O(n) size that answers queries in (Formula presented) time and O(1) working space, where (Formula presented) is the size of the alphabet, and the common substring must be a square, a periodic substring, a palindrome, or a Lyndon word.

開催年月日： 2019年10月

記述言語：英語  

開催地：Segovia   国名：スペイン  

We present the first worst-case linear time algorithm that directly computes the parameterized suffix and LCP arrays for constant sized alphabets. Previous algorithms either required quadratic time or the parameterized suffix tree to be built first. More formally, for a string over static alphabet and parameterized alphabet, our algorithm runs in time and O(n) words of space, where is the number of distinct symbols of in the string.

開催年月日： 2019年8月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Prague   国名：チェコ共和国  

開催年月日： 2019年8月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Prague   国名：チェコ共和国  

開催年月日： 2019年7月

記述言語：英語  

開催地：Pisa   国名：イタリア共和国  

For a string S, a palindromic substring S[i.j] is said to be a shortest unique palindromic substring (SUPS) for an interval [s, t] in S, if S[i.j] occurs exactly once in S, the interval [i, j] contains [s, t], and every palindromic substring containing [s, t] which is shorter than S[i.j] occurs at least twice in S. In this paper, we study the problem of answering SUPS queries on run-length encoded strings. We show how to preprocess a given run-length encoded string RLE_S of size m in O(m) space and O(mlog σRLE_S + m√log m/log logm) time so that all SUPSs for any subsequent query interval can be answered in O(√log m/log logm+ α) time, where α is the number of outputs, and σRLE_S is the number of distinct runs of RLE_S.

開催年月日： 2019年6月

記述言語：英語  

開催地：Pisa   国名：イタリア共和国  

A maximal repetition, or run, in a string, is a maximal periodic substring whose smallest period is at most half the length of the substring. In this paper, we consider runs that correspond to a path on a trie, or in other words, on a rooted edge-labeled tree where the endpoints of the path must be a descendant/ancestor of the other. For a trie with n edges, we show that the number of runs is less than n. We also show an O(n√log n log log n) time and O(n) space algorithm for counting and finding the shallower endpoint of all runs. We further show an O(n log n) time and O(n) space algorithm for finding both endpoints of all runs. We also discuss how to improve the running time even more.

開催年月日： 2019年6月

記述言語：英語  

開催地：Pisa   国名：イタリア共和国  

The suffix trees are fundamental data structures for various kinds of string processing. The suffix tree of a string T of length n has O(n) nodes and edges, and the string label of each edge is encoded by a pair of positions in T. Thus, even after the tree is built, the input text T needs to be kept stored and random access to T is still needed. The linear-size suffix tries (LSTs), proposed by Crochemore et al. [Linear-size suffix tries, TCS 638:171-178, 2016], are a “stand-alone” alternative to the suffix trees. Namely, the LST of a string T of length n occupies O(n) total space, and supports pattern matching and other tasks in the same efficiency as the suffix tree without the need to store the input text T. Crochemore et al. proposed an offline algorithm which transforms the suffix tree of T into the LST of T in O(nlog σ) time and O(n) space, where σ is the alphabet size. In this paper, we present two types of online algorithms which “directly” construct the LST, from right to left, and from left to right, without constructing the suffix tree as an intermediate structure. Both algorithms construct the LST incrementally when a new symbol is read, and do not access to the previously read symbols. The right-to-left construction algorithm works in O(nlog σ) time and O(n) space and the left-to-right construction algorithm works in O(n(log σ + log n/log log n)) time and O(n) space. The main feature of our algorithms is that the input text does not need to be stored.

開催年月日： 2019年6月

記述言語：英語  

開催地：Pisa   国名：イタリア共和国  

Lempel-Ziv (LZ) factorization and Lyndon factorization are well-known factorizations of strings. Recently, Kärkkäinen et al. studied the relation between the sizes of the two factorizations, and showed that the size of the Lyndon factorization is always smaller than twice the size of the non-overlapping LZ factorization [STACS 2017]. In this paper, we consider a similar problem for the overlapping version of the LZ factorization. Since the size of the overlapping LZ factorization is always smaller than the size of the non-overlapping LZ factorization and, in fact, can even be an O(log n) factor smaller, it is not immediately clear whether a similar bound as in previous work would hold. Nevertheless, in this paper, we prove that the size of the Lyndon factorization is always smaller than four times the size of the overlapping LZ factorization.

開催年月日： 2019年6月

記述言語：英語  

開催地：Pisa   国名：イタリア共和国  

Palindromes are important objects in strings which have been extensively studied from combinatorial, algorithmic, and bioinformatics points of views. Manacher [J. ACM 1975] proposed a seminal algorithm that computes the longest substring palindromes (LSPals) of a given string in O(n) time, where n is the length of the string. In this paper, we consider the problem of finding the LSPal after the string is edited. We present an algorithm that uses O(n) time and space for preprocessing, and answers the length of the LSPals in O(ℓ + log log n) time, after a substring in T is replaced by a string of arbitrary length ℓ. This outperforms the query algorithm proposed in our previous work [CPM 2018] that uses O(ℓ + log n) time for each query.

開催年月日： 2019年5月

記述言語：英語  

開催地：Rome   国名：イタリア共和国  

Let and be disjoint alphabets of respective size and. Two strings over of equal length are said to parameterized match (p-match) if there is a bijection such that (1) f is identity on and (2) f maps the characters of one string to those of the other string so that the two strings become identical. We consider the p-matching problem on a (reversed) trie and a string pattern P such that every path that p-matches P has to be reported. Let N be the size of the given trie. In this paper, we propose the parameterized position heap for that occupies O(N) space and supports p-matching queries in time, where m is the length of a query pattern P and is the number of paths in to report. We also present an algorithm which constructs the parameterized position heap for a given trie in time and working space.

開催年月日： 2019年3月

記述言語：英語  

開催地：Snowbird   国名：アメリカ合衆国  

We analyze the grammar generation algorithm of the RePair compression algorithm and show the relation between a grammar generated by RePair and maximal repeats. We reveal that RePair replaces step by step the most frequent pairs within the corresponding most frequent maximal repeats. Then, we design a novel variant of RePair, called MR-RePair, which substitutes the most frequent maximal repeats at once instead of substituting the most frequent pairs consecutively. We implemented MR-RePair and compared the size of the grammar generated by MR-RePair to that by RePair on several text corpora. Our experiments show that MR-RePair generates more compact grammars than RePair does, especially for highly repetitive texts.

開催年月日： 2018年10月

記述言語：英語  

開催地：Lima   国名：ペルー共和国  

We study a new generalization of palindromes and gapped palindromes called block palindromes. A block palindrome is a string that becomes a palindrome when identical substrings are replaced with a distinct character. We investigate several properties of block palindromes and in particular, study substrings of a string which are block palindromes. In so doing, we introduce the notion of a maximal block palindrome, which leads to a compact representation of all block palindromes that occur in a string. We also propose an algorithm which enumerates all maximal block palindromes that appear in a given string T in O(|T|+||MBP(T)||) time, where ||MBP(T)|| is the output size, which is optimal unless all the maximal block palindromes can be represented in a more compact way.

開催年月日： 2018年8月

記述言語：英語   会議種別：口頭発表（一般）  

国名：日本国  

開催年月日： 2018年7月

記述言語：英語  

開催地：Qingdao   国名：中華人民共和国  

A square is a non-empty string of form Y Y. The longest common square subsequence (LCSqS) problem is to compute a longest square occurring as a subsequence in two given strings A and B. We show that the problem can easily be solved in O(n⁶) time or O(|M|n⁴) time with O(n⁴) space, where n is the length of the strings and M is the set of matching points between A and B. Then, we show that the problem can also be solved in O(σ|M|³ + n) time and O(|M|² + n) space, or in O(|M|³ log² n log log n + n) time with O(|M|³ + n) space, where σ is the number of distinct characters occurring in A and B. We also study lower bounds for the LCSqS problem for two or more strings.

開催年月日： 2018年7月

記述言語：英語  

開催地：Qingdao   国名：中華人民共和国  

An Elastic-Degenerate String [Iliopoulus et al., LATA 2017] is a sequence of sets of strings, which was recently proposed as a way to model a set of similar sequences. We give an online algorithm for the Elastic-Degenerate String Matching (EDSM) problem that runs in O(nm √mlogm+ N) time and O(m) working space, where n is the number of elastic degenerate segments of the text, N is the total length of all strings in the text, and m is the length of the pattern. This improves the previous algorithm by Grossi et al. [CPM 2017] that runs in O(nm² + N) time.

開催年月日： 2009年7月

会議種別：口頭発表（一般）  

国名：日本国  

開催年月日： 2009年7月

会議種別：口頭発表（一般）  

国名：日本国  

開催年月日： 2006年10月

会議種別：口頭発表（一般）  

国名：日本国  

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Online   国名：その他  

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Online   国名：その他  

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Online   国名：その他  

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Online   国名：その他  

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Online   国名：その他  

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Online   国名：その他  

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Online   国名：その他  

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Online   国名：その他  

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Online   国名：その他  

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Chile (online)   国名：その他  

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Italy   国名：その他