九州大学 研究者情報
論文一覧
坂内 英夫(ばんない ひでお) データ更新日:2019.06.27

准教授 /  システム情報科学研究院 情報学部門 数理情報


原著論文
1. Akihiro Nishi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, O(n log n)-time Text Compression by LZ-style Longest First Substitution, Proceedings of The Prague Stringology Conference 2018, 12-26, 2018.08, [URL].
2. Isamu Furuya, Takuya Takagi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Takuya Kida, MR-RePair
Grammar Compression Based on Maximal Repeats, 2019 Data Compression Conference, DCC 2019
Proceedings - DCC 2019
2019 Data Compression Conference
, 10.1109/DCC.2019.00059, 508-517, 2019.05, [URL], 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..
3. Keisuke Goto, I. Tomohiro, Hideo Bannai, Shunsuke Inenaga, Block palindromes
A new generalization of palindromes, 25th International Symposium on String Processing and Information Retrieval, SPIRE 2018
String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings
, 10.1007/978-3-030-00479-8_15, 183-190, 2018.10, [URL], 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..
4. Yuki Kuhara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Recovering, counting and enumerating strings from forward and backward suffix arrays, 25th International Symposium on String Processing and Information Retrieval, SPIRE 2018
String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings
, 10.1007/978-3-030-00479-8_21, 254-267, 2018.10, [URL], The suffix array SAw of a string w of length n is a permutation of [1..n] such that SAw[i]=j iff w[j, n] is the lexicographically i-th suffix of w. In this paper, we consider variants of the reverse-engineering problem on suffix arrays with two given permutations P and Q of [1..n], such that P refers to the forward suffix array of some string w and Q refers to the backward suffix array of the reversed string wR. Our results are the following: (1) An algorithm which computes a solution string over an alphabet of the smallest size, in O(n) time. (2) The exact number of solution strings over an alphabet of size σ. (3) An efficient algorithm which computes all solution strings in the lexicographical order, in time near optimal up to log n factor..
5. Hiroe Inoue, Yuto Nakashima, Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Algorithms and combinatorial properties on shortest unique palindromic substrings, Journal of Discrete Algorithms, 10.1016/j.jda.2018.11.009, 52-53, 122-132, 2018.09, [URL], 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..
6. Takafumi Inoue, Shunsuke Inenaga, Heikki Hyyrö, Hideo Bannai, Masayuki Takeda, Computing longest common square subsequences, 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018
29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018
, 10.4230/LIPIcs.CPM.2018.15, 105, 15:1-15:13, 2018.07, [URL], 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(n6) time or O(|M|n4) time with O(n4) 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|3 + n) time and O(|M|2 + n) space, or in O(|M|3 log2 n log log n + n) time with O(|M|3 + 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..
7. Kotaro Aoyama, Yuto Nakashima, I. Tomohiro, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Faster online elastic degenerate string matching, 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018
29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018
, 10.4230/LIPIcs.CPM.2018.9, 9:1-9:10, 2018.07, [URL], 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(nm2 + N) time..
8. Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Longest lyndon substring after edit, 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018
29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018
, 10.4230/LIPIcs.CPM.2018.19, 19:1-19:10, 2018.07, [URL], 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..
9. Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Longest substring palindrome after edit, 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018
29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018
, 10.4230/LIPIcs.CPM.2018.12, 105, 12:1-12:14, 2018.07, [URL], 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 ℓ..
10. Isamu Furuya, Yuto Nakashima, I. Tomohiro, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Lyndon factorization of grammar compressed texts revisited, 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018
29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018
, 10.4230/LIPIcs.CPM.2018.24, 24:1-24:10, 2018.07, [URL], 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..
11. Hideo Bannai, Travis Gagie, I. Tomohiro, Online LZ77 parsing and matching statistics with RLBWTs, 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018
29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018
, 10.4230/LIPIcs.CPM.2018.7, 7:1-7:12, 2018.07, [URL], Lempel-Ziv 1977 (LZ77) parsing, matching statistics and the Burrows-Wheeler Transform (BWT) are all fundamental elements of stringology. In a series of recent papers, Policriti and Prezza (DCC 2016 and Algorithmica, CPM 2017) showed how we can use an augmented run-length compressed BWT (RLBWT) of the reverse T
R
of a text T, to compute offline the LZ77 parse of T in O(n log r) time and O(r) space, where n is the length of T and r is the number of runs in the BWT of T
R
. In this paper we first extend a well-known technique for updating an unaugmented RLBWT when a character is prepended to a text, to work with Policriti and Prezza's augmented RLBWT. This immediately implies that we can build online the LZ77 parse of T while still using O(n log r) time and O(r) space; it also seems likely to be of independent interest. Our experiments, using an extension of Ohno, Takabatake, I and Sakamoto's (IWOCA 2017) implementation of updating, show our approach is both time- and space-efficient for repetitive strings. We then show how to augment the RLBWT further -albeit making it static again and increasing its space by a factor proportional to the size of the alphabet -such that later, given another string S and O(log log n)-time random access to T, we can compute the matching statistics of S with respect to T in O(|S| log log n) time..
12. Rui Henriques, Alexandre P. Francisco, Luís M.S. Russo, Hideo Bannai, Order-preserving pattern matching indeterminate strings, 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018
29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018
, 10.4230/LIPIcs.CPM.2018.2, 2:1-2:15, 2018.07, [URL], Given an indeterminate string pattern p and an indeterminate string text t, the problem of orderpreserving pattern matching with character uncertainties (μOPPM) is to find all substrings of t that satisfy one of the possible orderings defined by p. When the text and pattern are determinate strings, we are in the presence of the well-studied exact order-preserving pattern matching (OPPM) problem with diverse applications on time series analysis. Despite its relevance, the exact OPPM problem suffers from two major drawbacks: 1) the inability to deal with indetermination in the text, thus preventing the analysis of noisy time series; and 2) the inability to deal with indetermination in the pattern, thus imposing the strict satisfaction of the orders among all pattern positions. In this paper, we provide the first polynomial algorithms to answer the μOPPM problem when: 1) indetermination is observed on the pattern or text; and 2) indetermination is observed on both the pattern and the text and given by uncertainties between pairs of characters. First, given two strings with the same length m and O(r) uncertain characters per string position, we show that the μOPPM problem can be solved in O(mr lg r) time when one string is indeterminate and r ∈ N+ and in O(m2) time when both strings are indeterminate and r=2. Second, given an indeterminate text string of length n, we show that μOPPM can be efficiently solved in polynomial time and linear space..
13. Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piakowski, Shiho Sugimoto, Diverse Palindromic Factorization is NP-Complete, International Journal of Foundations of Computer Science, 10.1142/S0129054118400014, 29, 2, 143-163, 2018.02, [URL], 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..
14. Shiho Sugimoto, Naoki Noda, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing abelian string regularities based on RLE, 28th International Workshop on Combinational Algorithms, IWOCA 2017
Combinatorial Algorithms - 28th International Workshop, IWOCA 2017, Revised Selected Papers
, 10.1007/978-3-319-78825-8_34, 420-431, 2018.01, [URL], 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 v1, …, vs of strings such that v1, …, vs-1 are all Abelian equivalent and vs is a substring of a permutation of v1, then w is said to have a regular Abelian period (p, t) where p = |v1| and t = |vs|. 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(m2n) time..
15. Yuto Nakashima, Hiroe Inoue, Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Shortest unique palindromic substring queries in optimal time, 28th International Workshop on Combinational Algorithms, IWOCA 2017
Combinatorial Algorithms - 28th International Workshop, IWOCA 2017, Revised Selected Papers
, 10.1007/978-3-319-78825-8_32, 397-408, 2018.01, [URL], 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..
16. Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Almost linear time computation of maximal repetitions in run length encoded strings, 28th International Symposium on Algorithms and Computation, ISAAC 2017
28th International Symposium on Algorithms and Computation, ISAAC 2017
, 10.4230/LIPIcs.ISAAC.2017.33, 92, 2017.12, [URL], 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..
17. Yuka Tanimura, Takaaki Nishimoto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Small-space LCE data structure with constant-time queries, 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017
42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017
, 10.4230/LIPIcs.MFCS.2017.10, 83, 2017.11, [URL], The longest common extension (LCE) problem is to preprocess a given string ω of length n so that the length of the longest common prefix between suffixes of ω that start at any two given positions is answered quickly. In this paper, we present a data structure of O(z2 + n/t ) words of space which answers LCE queries in O(1) time and can be built in O(n log δ) time, where 1 ≤ T ≤ √n is a parameter, z is the size of the Lempel-Ziv 77 factorization of ω and φ is the alphabet size. The proposed LCE data structure does not access the input string ω when answering queries, and thus w can be deleted after preprocessing. On top of this main result, we obtain further results using (variants of) our LCE data structure, which include the following: For highly repetitive strings where the z2 term is dominated by n/x, we obtain a constant-time and sub-linear space LCE query data structure. Even when the input string is not well compressible via Lempel-Ziv 77 factorization, we still can obtain a constant-time and sub-linear space LCE data structure for suitable and for φ ≤ 2o(log n). The time-space trade-off lower bounds for the LCE problem by Bille et al. [J. Discrete Algorithms, 25:42-50, 2014] and by Kosolobov [CoRR, abs/1611.02891, 2016] do not apply in some cases with our LCE data structure..
18. Kazuyuki Narisawa, Hideharu Hiratsuka, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Efficient Computation of Substring Equivalence Classes with Suffix Arrays, Algorithmica, 10.1007/s00453-016-0178-z, 79, 2, 291-318, 2017.10, [URL], 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 O(nlog σ) time, where σ 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..
19. Hideo Bannai, I. Tomohiro, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, Kazuya Tsuruta, The "runs" theorem, SIAM Journal on Computing, 10.1137/15M1011032, 46, 5, 1501-1514, 2017.09, [URL], We give a new characterization of maximal repetitions (or runs) in strings based on Lyndon words. The characterization leads to a proof of what was known as the "runs" conjecture [R. M. Kolpakov andG.Kucherov, Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Los Alamitos, CA, 1999, pp. 596-604]), which states that the maximum number of runs ρ(n) in a string of length n is less than n. The proof is remarkably simple, considering the numerous endeavors to tackle this problem in the last 15 years, and significantly improves our understanding of how runs can occur in strings. In addition, we obtain an upper bound of 3n for the maximum sum of exponents σ(n) of runs in a string of length n, improving on the best known bound of 4.1n by Crochemore et al. [J. Discrete Algorithms, 14 (2012), pp. 29-36], as well as other improved bounds on related problems. The characterization 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. We also establish a relationship between runs and nodes of the Lyndon tree, which gives a simple optimal solution to the 2-period query problem that was recently solved by Kociumaka et al. [Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA) 2015, San Diego, CA, SIAM, Philadelphia, 2015, pp. 532-551]..
20. Yuto Nakashima, Takashi Okabe, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Inferring strings from Lyndon factorization, Theoretical Computer Science, 10.1016/j.tcs.2017.05.038, 2017.08, The Lyndon factorization of a string w is a unique factorization ℓ1p1,...,ℓmpm of w such that ℓ1,...,ℓ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=((s1,p1),...,(sm,pm)) 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 ℓ1p1,...,ℓmpm with |ℓi|=si 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..
21. Hideo Bannai, Shunsuke Inenaga, Dominik Köppl, Computing all distinct squares in linear time for integer alphabets, 28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017
28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017
, 10.4230/LIPIcs.CPM.2017.22, 78, 2017.07, [URL], Given a string on an integer alphabet, we present an algorithm that computes the set of all distinct squares belonging to this string in time linear in the string length. As an application, we show how to compute the tree topology of the minimal augmented suffix tree in linear time. Asides from that, we elaborate an algorithm computing the longest previous table in a succinct representation using compressed working space..
22. Keita Kuboi, Yuta Fujishige, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Faster STR-IC-LCS Computation via RLE, 28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017
28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017
, 10.4230/LIPIcs.CPM.2017.20, 78, 2017.07, [URL], The constrained LCS problem asks one to find a longest common subsequence of two input strings A and B with some constraints. The STR-IC-LCS problem is a variant of the constrained LCS problem, where the solution must include a given constraint string C as a substring. Given two strings A and B of respective lengths M and N, and a constraint string C of length at most min{M, N}, the best known algorithm for the STR-IC-LCS problem, proposed by Deorowicz (Inf. Process. Lett., 11:423-426, 2012), runs in O(MN) time. In this work, we present an O(mN+nM)-time solution to the STR-IC-LCS problem, where m and n denote the sizes of the run-length encodings of A and B, respectively. Since m ≤ M and n ≤ N always hold, our algorithm is always as fast as Deorowicz's algorithm, and is faster when input strings are compressible via RLE..
23. Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Tight bounds on the maximum number of shortest unique substrings, 28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017
28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017
, 10.4230/LIPIcs.CPM.2017.24, 78, 2017.07, [URL], A substring Q of a string S is called a shortest unique substring (SUS) for interval [s, t] in S, if Q occurs exactly once in S, this occurrence of Q contains interval [s, t], and every substring of S which contains interval [s, t] and is shorter than Q occurs at least twice in S. The SUS problem is, given a string S, to preprocess S so that for any subsequent query interval [s, t] all the SUSs for interval [s, t] can be answered quickly. When s = t, we call the SUSs for [s, t] as point SUSs, and when s ≤ t, we call the SUSs for [s, t] as interval SUSs. There exist optimal O(n)-time preprocessing scheme which answers queries in optimal O(k) time for both point and interval SUSs, where n is the length of S and k is the number of outputs for a given query. In this paper, we reveal structural, combinatorial properties underlying the SUS problem: Namely, we show that the number of intervals in S that correspond to point SUSs for all query positions in S is less than 1.5n, and show that this is a matching upper and lower bound. Also, we consider the maximum number of intervals in S that correspond to interval SUSs for all query intervals in S..
24. Yohei Ueki, Diptarama, Masatoshi Kurihara, Yoshiaki Matsuoka, Kazuyuki Narisawa, Ryo Yoshinaka, Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings, Proceedings of the 43rd International Conference on Current Trends in Theory and Practice of Computer Science, 10.1007/978-3-319-51963-0_28, 363-374, 2017.01.
25. Temma Nakamura, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Order preserving pattern matching on trees and DAGs, 24th International Symposium on String Processing and Information Retrieval, SPIRE 2017
String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Proceedings
, 10.1007/978-3-319-67428-5_23, 10508 LNCS, 271-277, 2017.01, [URL], The order preserving pattern matching (OPPM) problem is, given a pattern string p and a text string t, find all substrings of t which have the same relative orders as p. In this paper, we consider two variants of the OPPM problem where a set of text strings is given as a tree or a DAG. We show that the OPPM problem for a single pattern p of length m and a text tree T of size N can be solved in O(m+N) time with O(m) working space if the characters of p are drawn from an integer alphabet of polynomial size. The time complexity becomes O(m log m + N) if the pattern p is over a general ordered alphabet. We then show that the OPPM problem for a single pattern and a text DAG is NP-complete..
26. Yoshiaki Matsuoka, Takahiro Aoki, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Generalized pattern matching and periodicity under substring consistent equivalence relations, THEORETICAL COMPUTER SCIENCE, 10.1016/j.tcs.2016.02.017, 656, 225-233, 2016.12.
27. Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Faster Lyndon factorization algorithms for SLP and LZ78 compressed text, THEORETICAL COMPUTER SCIENCE, 10.1016/j.tcs.2016.03.005, 656, 215-224, 2016.12.
28. Golnaz Badkobeh, Hideo Bannai, Keisuke Goto, Tomohiro I, Costas S. Iliopoulos, Shunsuke Inenaga, Simon J. Puglisi, Shiho Sugimoto, Closed factorization, DISCRETE APPLIED MATHEMATICS, 10.1016/j.dam.2016.04.009, 212, 23-29, 2016.10.
29. Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Dynamic Index and LZ Factorization in Compressed Space, Proceedings of The Prague Stringology Conference 2016 (PSC 2016), 158-171, 2016.08.
30. Hiroe Inoue, Yoshiaki Matsuoka, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Smallest and Largest Repetition Factorizations in O(n log n) Time, Proceedings of The Prague Stringology Conference 2016 (PSC 2016), 135-145, 2016.08.
31. Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Fully Dynamic Data Structure for LCE Queries in Compressed Space, Proceedings of 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), 10.4230/LIPIcs.MFCS.2016.72, 72:1-72:15, 2016.08, [URL].
32. Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Shortest Unique Substring Queries on Run-Length Encoded Strings, Proceedings of 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), 10.4230/LIPIcs.MFCS.2016.69, 69:1-69:11, 2016.08, [URL].
33. Yuta Fujishige, Yuki Tsujimaru, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing DAWGs and Minimal Absent Words in Linear Time for Integer Alphabets, Proceedings of 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), 10.4230/LIPIcs.MFCS.2016.38, 38:1-38:14, 2016.08, [URL].
34. Yuta Fujishige, Michitaro Nakamura, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Finding Gapped Palindromes Online, Proceedings of the 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), 10.1007/978-3-319-44543-4_15, 2016.08.
35. Yoshiaki Matsuoka, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Factorizing a String into Squares in Linear Time, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), 10.4230/LIPIcs.CPM.2016.27, 27:1-27:12, 2016.06, [URL].
36. Yuka Tanimura, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Simon J. Puglisi, Masayuki Takeda, Deterministic Sub-Linear Space LCE Data Structures With Efficient Construction, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), 10.4230/LIPIcs.CPM.2016.1, 1:1-1:10, 2016.06, [URL].
37. Makoto Nishida, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Inferring Strings from Full Abelian Periods, Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC 2015), 10.1007/978-3-662-48971-0_64, 768-779, 2015.12.
38. Yuka Tanimura, Yuta Fujishige, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, A Faster Algorithm for Computing Maximal alpha-gapped Repeats in a String, Proceedings of the 22nd International Symposium on String Processing and Information Retrieval (SPIRE 2015), 10.1007/978-3-319-23826-5_13, 124-136, 2015.09.
39. Hideo Bannai, Shunsuke Inenaga, Tomasz Kociumaka, Arnaud Lefebvre, Jakub Radoszewski, Wojciech Rytter, Shiho Sugimoto, Tomasz Walen, Efficient Algorithms for Longest Closed Factor Array, Proceedings of the 22nd International Symposium on String Processing and Information Retrieval (SPIRE 2015), 10.1007/978-3-319-23826-5_10, 95-102, 2015.09.
40. Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Constructing LZ78 tries and position heaps in linear time for large alphabets, INFORMATION PROCESSING LETTERS, 10.1016/j.ipl.2015.04.002, 115, 9, 655-659, 2015.09.
41. Takaaki Nishimoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Left-Right Maximal Generic Words, Proceedings of The Prague Stringology Conference 2015 (PSC 2015), 5-16, 2015.08.
42. Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski, Simon J. Puglisi, Shiho Sugimoto, Diverse Palindromic Factorization Is NP-complete, Proceedings of the 19th International Conference on Developments in Language Theory (DLT 2015), 10.1007/978-3-319-21500-6_6, 85-96, 2015.07.
43. Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding, Proceedings of the 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015), 10.1007/978-3-319-19929-0_19, 219-230, 2015.06.
44. Yoshiaki Matsuoka, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Semi-dynamic compact index for short patterns and succinct van Emde Boas tree, Proceedings of the 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015), 10.1007/978-3-319-18173-8_29, 355-366, 2015.06.
45. Yuya Tamakoshi, Keisuke Goto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, An opportunistic text indexing structure based on run length encoding, Proceedings of the 9th International Conference on Algorithms and Complexity (CIAC 2015), 10.1007/978-3-319-18173-8_29, 390-402, 2015.05.
46. Tomohiro I, Takaaki Nishimoto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Compressed automata for dictionary matching, THEORETICAL COMPUTER SCIENCE, 10.1016/j.tcs.2015.01.019, 578, 30-41, 2015.05.
47. Tomohiro I, Wataru Matsubara, Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Kazuyuki Narisawa, Ayumi Shinohara, Detecting regularities on grammar-compressed strings, INFORMATION AND COMPUTATION, 10.1016/j.ic.2014.09.009, 240, 74-89, 2015.02.
48. Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, Kazuya Tsuruta, A new characterization of maximal repetitions by Lyndon trees, Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '15), 10.1137/1.9781611973730.38, 562-571, 2015.01, 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 $
ho(n)$ in a string of length $n$. Furthermore, we show an upper bound of $
ho(n) < 1.5n$, which improves on the best upper bound $1.6n$ (Crochemore & Ilie 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 {em not} utilize the Lempel-Ziv factorization of the string..
49. Golnaz Badkobeh, Hideo Bannai, Keisuke Goto, Tomohiro I, Costas S. Iliopoulos, Shunsuke Inenaga, Simon J. Puglisi, Shiho Sugimoto, Closed Factorization, Proceedings of The Prague Stringology Conference 2014 (PSC 2014), 162-168, 2014.09, 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..
50. Shohei Matsuda, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Abelian Covers and Abelian Runs, Proceedings of The Prague Stringology Conference 2014 (PSC 2014), 43-51, 2014.09, Two strings u and v are said to be Abelian equivalent if u is a permutation of the characters of v. We introduce two new regularities on strings w.r.t. Abelian equivalence, called Abelian covers and Abelian runs, which are generalizations of covers and runs of strings, respectively. We show how to determine in O(n) time whether or not a given string w of length n has an Abelian cover. Also, we show how to compute an O(n^2)-size representation of (possibly exponentially many) Abelian covers of w in O(n^2) time. Moreover, we present how to compute all Abelian runs in w in O(n^2) time, and state that the maximum number of all Abelian runs in a string of length n is Omega(n^2)..
51. Yuto Nakashima, Takashi Okabe, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Inferring Strings from Lyndon factorization, Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014), 10.1007/978-3-662-44465-8_48, 565-576, 2014.08, The Lyndon factorization of a string $w$ is a unique factorization $ell_1^{p_1}, ldots, ell_m^{p_m}$ of $w$ s.t. $ell_1, dots, ell_m$ is a sequence of Lyndon words that is monotonically decreasing in lexicographic order. In this paper, we consider the emph{reverse-engineering problem on Lyndon factorization}: Given a sequence $S = ((s_1, p_1), ldots, (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 $ell_1^{p_1}, ldots, ell_m^{p_m}$ with $|ell_i| = s_i$ for all $1 leq i leq 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$..
52. Tomohiro I, Shiho Sugimoto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Palindromic Factorizations and Palindromic Covers On-line, Proceedings of the 25th Annual Symposium on Combinatorial Pattern Matching (CPM 2014), 10.1007/978-3-319-07566-2_16, 150-161, 2014.06, 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..
53. Jun'ichi Yamamoto, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Faster Compact On-Line Lempel-Ziv Factorization, Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS 2014), 10.4230/LIPIcs.STACS.2014.675, 675-678, 2014.03.
54. Keisuke Goto and Hideo Bannai, Space Efficient Linear Time Lempel-Ziv Factorization for Small Alphabets, Data Compression Conference 2014 (DCC 2014), 10.1109/DCC.2014.62, 163-172, 2014.03.
55. Eiichi Bannai, Etsuko Bannai, Hideo Bannai, On the existence of tight relative 2-designs on binary Hamming association schemes, Discrete Mathematics, 10.1016/j.disc.2013.09.013, 314, 6, 17-37, 2014.01, [URL].
56. Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Inferring strings from suffix trees and links on a binary alphabet, Discrete Applied Mathematics, 10.1016/j.dam.2013.02.033, 163(3):316-325, 2014.01, [URL], 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..
57. Kazuya Tsuruta, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Shortest Unique Substrings Queries in Optimal Time, Proceedings of the 40th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2014), 10.1007/978-3-319-04298-5_44, Lecture Notes in Computer Science 8327:503-513, 2014.01.
58. Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Faster Lyndon factorization algorithms for SLP and LZ78 compressed text, Proceedings of the 20th International Symposium on String Processing and Information Retrieval (SPIRE 2013), 10.1007/978-3-319-02432-5_21, Lecture Notes in Computer Science 8214:174-185, 2013.10.
59. Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Reversed Lempel-Ziv Factorization Online, Proceedings of The Prague Stringology Conference 2013 (PSC 2013), 107-118, 2013.09.
60. Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Kazuyuki Narisawa, Ayumi Shinohara, Detecting Regularities on Grammar-compressed Strings, Proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science (MFCS 2013), 10.1007/978-3-642-40313-2_51, Lecture Notes in Computer Science 8087, 571-582, Lecture Notes in Computer Science 8087:571-582, 2013.08.
61. Tomohiro I, Takaaki Nishimoto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Compressed Automata for Dictionary Matching, Proceedings of the 18th International Conference on Implementation and Application of Automata (CIAA 2013),, 2013.07.
62. Hideo Bannai, Pawel Gawrychowski, Shunsuke Inenaga and Masayuki Takeda, Converting SLP to LZ78 in almost linear time, Proceedings of the 24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013), 2013.06.
63. Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Efficient Lyndon factorization of grammar compressed text, Proceedings of the 24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013), 2013.06.
64. Toshiya Tanaka, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Computing convolution on grammar-compressed text, Data Compression Conference 2013 (DCC 2013), 451-460, 2013.03.
65. Yuya Tamakoshi, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, From Run Length Encoding to LZ78 and Back Again, Data Compression Conference 2013 (DCC 2013), 143-152, 2013.03.
66. Keisuke Goto and Hideo Bannai, Simpler and Faster Lempel Ziv Factorization, Data Compression Conference 2013 (DCC 2013), 133-142, 2013.03.
67. Takashi Katsura, Kazuyuki Narisawa, Ayumi Shinohara, Hideo Bannai and Shunsuke Inenaga, Permuted pattern matching on multi-track strings, Proceedings of the 38th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2013), 10.1007/978-3-642-35843-2_25, Lecture Notes in Computer Science 7741:280-291, 2013.01, [URL].
68. Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Fast q-gram mining on SLP compressed strings, Journal of Discrete Algorithms, http://dx.doi.org/10.1016/j.jda.2012.07.006, 18, 89-99, 2013.01, [URL], 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..
69. Yoko Anan, Kohei Hatano, Hideo Bannai, Masayuki Takeda, and Ken Satoh, Polyphonic Music Classification on Symbolic Data using Dissimilarity Functions, Proceedings of the 13th International Society for Music Information Retrieval Conference (ISMIR 2012), 229-234, 2012.10, [URL].
70. Kazuhito Hagio, Takashi Ohgami, Hideo Bannai, and Masayuki Takeda, Eager XPath Evaluation over XML Streams, Proceedings of the 19th International Symposium on String Processing and Information Retrieval (SPIRE 2012), 10.1007/978-3-642-34109-0_26, Lecture Notes in Computer Science 7608:245-250, 2012.10, [URL].
71. Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, The position heap of a trie, Proceedings of the 19th International Symposium on String Processing and Information Retrieval (SPIRE 2012), 10.1007/978-3-642-34109-0_38, Lecture Notes in Computer Science 7608:360-371, 2012.10, [URL].
72. Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Efficient LZ78 factorization of grammar compressed text, Proceedings of the 19th International Symposium on String Processing and Information Retrieval (SPIRE 2012), 10.1007/978-3-642-34109-0_10, 2012.10, [URL].
73. Hideo Bannai, Travis Gagie, Tomohiro I, Shunsuke Inenaga, Gad M. Landau, Moshe Lewenstein, An Efficient Algorithm to Test Square-Freeness of Strings Compressed by Straight-Line Programs, Information Processing Letters, 10.1016/j.ipl.2012.06.017, 112, 19, 711-714, 2012.10, [URL].
74. Tomohiro I, Yuki Enokuma, Hideo Bannai, and Masayuki Takeda, General Algorithms for Mining Closed Flexible Patterns under Various Equivalence Relations, Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD 2012), 10.1007/978-3-642-33486-3_28, Lecture Notes in Computer Science 7524:435-450, 2012.09, [URL].
75. Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Speeding up q-gram mining on grammar-based compressed texts, Proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching (CPM 2012), 10.1007/978-3-642-31265-6_18, Lecture Notes in Computer Science 7354:220-231, 2012.07, [URL].
76. Shunsuke Inenaga, Hideo Bannai, Finding Characteristic Substrings from Compressed Texts, International Journal of Foundations of Computer Science, 10.1142/S0129054112400126, 23, 2, 261-280, 2012.02, [URL].
77. Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Computing q-gram Non-overlapping Frequencies on SLP Compressed Texts, Proceedings of the 38th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2012), 10.1007/978-3-642-27660-6_25, Lecture Notes in Computer Science 7147:301-312, 2012.01.
78. Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Verifying and enumerating parameterized border arrays, Theoretical Computer Science, doi:10.1016/j.tcs.2011.09.008, 412, 50, 6959-6981, 2011.11.
79. Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Fast q-gram Mining on SLP Compressed Strings, Proceedings of the 18th International Symposium on String Processing and Information Retrieval (SPIRE 2011), 10.1007/978-3-642-24583-1_27, Lecture Notes in Computer Science 7024:135-146, 2011.10.
80. Kazuhito Hagio, Takashi Ohgami, Hideo Bannai, Masayuki Takeda, Efficient Eager XPath Filtering over XML Streams, Proceedings of The Prague Stringology Conference 2011 (PSC 2011), 30-44, 2011.08, [URL].
81. Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Inferring Strings from Suffix Trees and Links on a Binary Alphabet, Proceedings of The Prague Stringology Conference 2011 (PSC 2011), 121-130, 2011.08, [URL].
82. Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Longest Common Substring/Subsequence of Non-linear Texts, Proceedings of The Prague Stringology Conference 2011 (PSC 2011), 197-208, 2011.08, [URL].
83. Takanori Yamamoto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Faster Subsequence and Don't-Care Pattern Matching on Compressed Texts, Proceedings of the 22nd Annual Symposium on Combinatorial Pattern Matching (CPM 2011), 10.1007/978-3-642-21458-5_27, Lecture Notes in Computer Science 6661:309-322, 2011.06.
84. Kazuaki Kashihara, Kohei Hatano, Hideo Bannai, Masayuki Takeda, Sparse Substring Pattern Set Discovery using Linear Programming Boosting, Proceedings of the 13th International Conference on Discovery Science (DS 2010), 10.1007/978-3-642-16184-1_10, Lecture Notes in Computer Science 6332:132-143, 2010.10.
85. Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Counting and Verifying Maximal Palindromes, Proceedings of the 17th International Symposium on String Processing and Information Retrieval (SPIRE 2010), 10.1007/978-3-642-16321-0_13, Lecture Notes in Computer Science 6393:135-146, 2010.10.
86. Hideo Bannai, Mathieu Giraud, Kazuhiko Kusano, Wataru Matsubara, Ayumi Shinohara, Jamie Simpson, The Number of Runs in a Ternary Word, Proceedings of The Prague Stringology Conference 2010 (PSC 2010), 178-181, 2010.08, [URL].
87. Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Verifying a Parameterized Border Array in O(n^1.5) Time, Proceedings of the 21st Annual Symposium on Combinatorial Pattern Matching (CPM 2010), 10.1007/978-3-642-13509-5_22, Lecture Notes in Computer Science 6129: 238-250, 2010.06, [URL].
88. Ryosuke Nakamura, Shunsuke Inenaga, Hideo Bannai, Takashi Funamoto, Masayuki Takeda, and Ayumi Shinohara, Linear-Time Text Compression by Longest-First Substitution, Algorithms, 10.3390/a2041429, 2, 4, 1429-1448, 2009.11, [URL].
89. Takanori Yamamoto, Hideo Bannai, Masao Nagasaki, and Satoru Miyano, Better Decomposition Heuristics for the Maximum-Weight Connected Graph Problem using Betweenness Centrality, Proceedings of the 12th International Conference on Discovery Science (DS2009), Lecture Notes in Computer Science 5808:465-472, 2009.10, [URL].
90. Kazunori Hirashima, Hideo Bannai, Wataru Matsubara, Akira Ishino and Ayumi Shinohara, Bit-parallel algorithms for computing all the runs in a string, Proceedings of The Prague Stringology Conference 2009 (PSC 2009), 203-213, 2009.09, [URL].
91. Shunsuke Inenaga and Hideo Bannai, Finding Characteristic Substrings from Compressed Texts, Proceedings of The Prague Stringology Conference 2009 (PSC 2009), 40–54, 2009.09, [URL].
92. Tomohiro I, Satoshi Deguchi, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Lightweight Parameterized Suffix Array Construction, Proceedings of the 20th International Workshop on Combinatorial Algorithms (IWOCA 2009), 2009.06.
93. Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Counting Parameterized Border Arrays for a Binary Alphabet, Proceedings of the 3rd International Conference on Language and Automata Theory and Applications (LATA 2009), Lecture Notes in Computer Science 5457: 422-433, 2009.04, [URL].
94. Wataru Matsubara, Kazuhiko Kusano, Hideo Bannai and Ayumi Shinohara, A Series of Run-Rich Strings, Proceedings of the 3rd International Conference on Language and Automata Theory and Applications (LATA 2009), Lecture Notes in Computer Science 5457: 578-587, 2009.04, [URL].
95. Yoshimi Yashiro, Hideo Bannai, Takashi Minowa, Tomohide Yabiku, Satoru Miyano, Mitsujiro Osawa, Atsushi Iwama and Hiromitsu Nakauchi, Transcriptional profiling of hematopoietic stem cells by high-throughput sequencing, International Journal of Hematology, 89(1):24-33, 2009.01, [URL].
96. Kazuyuki Narisawa, Hideo Bannai, Kohei Hatano, Shunsuke Inenaga, Masayuki Takeda, String Kernels Based on Variable-Length-Don't-Care Patterns, Proceedings of the 11th International Conference on Discovery Science (DS2008), LNAI 5255:308-318, 2008.10, [URL].
97. Satoshi Deguchi, Fumihito Higashijima, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Parameterized Suffix Arrays for Binary Strings, Proceedings of The Prague Stringology Conference 2008 (PSC2008), 84-94, 2008.09, [URL].
98. Kazuhiko Kusano, Wataru Matsubara, Akira Ishino, Hideo Bannai and Ayumi Shinohara, New Lower Bounds for the Maximum Number of Runs in a String, Proceedings of The Prague Stringology Conference 2008 (PSC2008), 140-145, 2008.09, [URL].
99. Eiichi Bannai, Etsuko Bannai, and Hideo Bannai, Uniqueness of Certain Association Schemes, European Journal of Combinatorics, 29(6):1379-1395, 2008.08, [URL].
100. Yasuto Higa, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Reachability on Suffix Tree Graphs, International Journal of Foundations of Computer Science, 19(1):147-162, 2008.02.
101. Kazuyuki Narisawa, Hideo Bannai, Kohei Hatano, and Masayuki Takeda, Unsupervised Spam Detection based on String Alienness Measures, In Proceedings of the 10th International Conference on Discovery Science (DS2007), Lecture Notes in Computer Science 4755:161-172, 2007.10.
102. Kazuyuki Narisawa, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Efficient Computation of Substring Equivalence Classes with Suffix Array, Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching (CPM 2007), Lecture Notes in Computer Science 4580:340-351, 2007.07.
103. Tatsuya Akutsu, Hideo Bannai, Satoru Miyano, and Sascha Ott, On the Complexity of Deriving Position Specific Score Matrices from Positive and Negative Sequences, Discrete Applied Mathematics, 155:676-685, 2007.04.
104. Ryosuke Nakamura, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Simple Linear-Time Off-Line Text Compression by Longest-First Substitution, Data Compression Conference (DCC 2007), 123-132, 2007.03.
105. Yasuto Higa, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, A New Family of String Classifiers based on Local Relatedness, Proceedings of the 9th International Conference on Discovery Science (DS2006), Lecture Notes in Artificial Intelligence 4265:114-124, 2006.10.
106. Yoshio Takei, Akatsuki Kawakoshi, Takehiro Tsukada, Shinya Yuge, Maho Ogoshi, Koji Inoue, Susumu Hyodo, Hideo Bannai, and Satoru Miyano, Contribution of Comparative Fish Studies to General Endocrinology: Structure and Function of Some Osmoregulatory Hormones, Journal of Experimental Zoology Part A: Comparative Experimental Biology, 35(9):787-798, 2006.09.
107. Yasuto Higa, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Reachability on Suffix Tree Graphs, Proceedings of The Prague Stringology Conference '06 (PSC'06), 212-225, 2006.08.
108. Hideo Bannai, Kohei Hatano, Shunsuke Inenaga, Masayuki Takeda, Practical Algorithms for Pattern Based Linear Regression, Proceedings of the 8th International Conference on Discovery Science, 3735, 44-56, Lecture Notes in Artificial Intelligence 3735:44-56, 2005.10.
109. Osamu Hirose, Naoki Nariai, Yoshinori Tamada, Hideo Bannai, Seiya Imoto, and Satoru Miyano, Estimating Gene Networks from Expression Data and Binding Location Data via Boolean Networks, Proceedings of the First International Workshop on Data Mining and Bioinformatics (DMBIO2005), Lecture Notes in Computer Science 3482:349-356, 2005.05.
110. Yoshinori Tamada, Hideo Bannai, Seiya Imoto, Toshiaki Katayama, Minoru Kanehisa, and Satoru Miyano, Utilizing Evolutionary Information and Gene Expression Data for Estimating Gene Networks with Bayesian Network Models, Journal of Bioinformatics and Computational Biology, 3(6):1295-1313, 2005.01.
111. Hideo Bannai, Heikki Hyyro, Ayumi Shinohara, Masayuki Takeda, Kenta Nakai, and Satoru Miyano, An O(N^2) Algorithm for Discovering Optimal Boolean Pattern Pairs, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 10.1109/TCBB.2004.36, 1, 4, 159-170, 1(4): 159-170, 2004.12.
112. Shunsuke Inenaga, Hideo Bannai, Heikki Hyyro, Ayumi Shinohara, Masayuki Takeda, Kenta Nakai, and Satoru Miyano, Finding Optimal Pairs of Cooperative and Competing Patterns with Bounded Distance, Proceedings of the 7th International Conference on Discovery Science (DS 2004), 3245, 32-46, Lecture Notes in Artificial Intelligence 3245:32-46, 2004.10.
113. Hideo Bannai, Heikki Hyyro, Ayumi Shinohara, Masayuki Takeda, Kenta Nakai, and Satoru Miyano, Finding Optimal Pairs of Patterns, Proceedings of the 4th International Workshop on Algorithms in Bioinformatics (WABI 2004), 3240, 450-462, Lecture Notes in Bioinformatics 3240:450-462, 2004.09.
114. Yoshio Takei, Koji Inoue, Maho Ogoshi, Tetsushi Kawahara, Hideo Bannai, and Satoru Miyano, Identification of Novel Adrenomedullin in Mammals: A Potent Cardiovascular and Renal Regulator, FEBS Letters, 556:53-58, 2004.01.
115. Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, and Satoru Miyano, Efficiently Finding Regulatory Elements using Correlation with Gene Expression, Journal of Bioinformatics and Computational Biology, 2(2):273-288, 2004.01.
116. Masayuki Takeda, Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, and Setsuo Arikawa, Discovering Most Classificatory Patterns for Very Expressive Pattern Classes, Proceedings of the 6th International Conference on Discovery Science (DS 2003), 2843, 486-493, Lecture Notes in Artificial Intelligence 2843:486-493, 2003.10.
117. Eijiro Sumii, Hideo Bannai, The Extension of ML with Hypothetical Views for Discovery Science: Formalization and Implementation, Journal of Functional and Logic Programming, Special Issue 1, 2003.01, [URL].
118. Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, and Masayuki Takeda, Inferring Strings from Graphs and Arrays, Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science, 2747, 208-217, Lecture Notes in Computer Science 2747:208-217, 2003.01.
119. Yoshinori Tamada, Sunyong Kim, Hideo Bannai, Seiya Imoto, Kousuke Tashiro, Satoru Kuhara, and Satoru Miyano, Estimating Gene Networks from Gene Expression Data by Combining Bayesian Network Model with Promoter Element Detection, Bioinformatics, 10.1093/bioinformatics/btg1082, 19, II227-II236, 19(Suppl.2):ii227-ii236, 2003.01.
120. Sascha Ott, Yoshinori Tamada, Hideo Bannai, Kenta Nakai, and Satoru Miyano, Intrasplicing: Analysis of Long Intron Sequences, Proceedings of the 8th Pacific Symposium on Biocomputing (PSB2003), 8:339-350, 2003.01.
121. Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, and Satoru Miyano, A String Pattern Regression Algorithm and Its Application to Pattern Discovery in Long Introns, Genome Informatics, 13:3-11, 2002.12.
122. Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, Masayuki Takeda, and Setsuo Arikawa, Discovering Best Variable-Length-Don't-Care Patterns, Proceedings of the 5th International Conference on Discovery Science (DS2002), 2534, 86-97, Lecture Notes in Artificial Intelligence 2534:86-97, 2002.11.
123. Eijiro Sumii, Hideo Bannai, VMlambda: A Functional Calculus for Scientific Discovery, Proceedings of the 6th International Symposium on Functional and Logic Programming (FLOPS 2002), Lecture Notes in Computer Science 2441:290-304, 2002.09.
124. Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Hideo Bannai, and Setsuo Arikawa, Space-Economical Construction of Index Structures for All Suffixes of a String, Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science (MFCS2002), 2420, 341-352, Lecture Notes in Computer Science 2420:341-352, 2002.08.
125. Tatsuya Akutsu, Hideo Bannai, Satoru Miyano, Sacha Ott, On the Complexity of Deriving Position Specific Score Matrices from Examples, Proceedings of the 13th Annual Symposium on Combinatorial Pattern Matching (CPM2002), Lecture Notes in Computer Science 2373:168-177, 2002.07.
126. Osamu Maruyama, Satoru Kuhara, Hideo Bannai, Satoru Miyano and Yoshinori Tamada, Fast algorithm for extracting multiple unordered short motifs using bit operations, Proceedings of the 6th Joint Conference on Information Science (JCIS 2002), 1180-1185, 1180-1185, 2002.03.
127. Osamu Maruyama, Hideo Bannai, Yoshinori Tamada, Satoru Kuhara, and Satoru Miyano, Fast Algorithm for Extracting Multiple Unordered Short Motifs Using Bit Operations, Information Sciences, 10.1016/S0020-0255(02)00219-0, 146, 1-4, 115-126, 146(1-4):115-126, 2002.01.
128. Hideo Bannai, Yoshinori Tamada, Osamu Maruyama, Kenta Nakai, and Satoru Miyano, Extensive Feature Detection of N-Terminal Protein Sorting Signals, Bioinformatics, 10.1093/bioinformatics/18.2.298, 18, 2, 298-305, 18(2):298-305, 2002.01.
129. Hideo Bannai, Yoshinori Tamada, Osamu Maruyama, and Satoru Miyano, VML: A View Modeling Language for Computational Knowledge Discovery, Proceedings of the 4th International Conference on Discovery Science (DS2001), Lecture Notes in Artificial Intelligence 2226:30-44, 2001.11.
130. Toru Nakayashiki, Kanae Ebihara, Hideo Bannai, and Yoshikazu Nakamura, Yeast [PSI+] ''Prions'' that Are Crosstransmissible and Susceptible beyond a Species Barrier through a Quasi-Prion State, Molecular Cell, 7(6):1121-1130, 2001.06.
131. Hideo Bannai, Yoshinori Tamada, Osamu Maruyama, Kenta Nakai, and Satoru Miyano, Views: Fundamental Building Blocks in the Process of Knowledge Discovery, Proceedings of the 14th International FLAIRS Conference, 233-238, 2001.05.
132. Hideo Bannai, Yoshinori Tamada, Osamu Maruyama, and Satoru Miyano, Concepts for Accelerating the Computational Knowledge Discovery Process, Linkoping Electronic Articles in Computer and Information Science, 2001.01, [URL].
133. Tomohiro Yasuda, Hideo Bannai, Shuichi Onami, Satoru Miyano, Hiroaki Kitano, Towards Automatic Construction of Cell-Lineage of C. elegans from Nomarski DIC Microscope Images, Genome Informatics, 10:144-154, 1999.12.

九大関連コンテンツ

pure2017年10月2日から、「九州大学研究者情報」を補完するデータベースとして、Elsevier社の「Pure」による研究業績の公開を開始しました。
 
 
九州大学知的財産本部「九州大学Seeds集」