1. |
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, 2017.07, 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_{1}, …, vs of strings such that v_{1}, …, v_{s-1} are all Abelian equivalent and vs is a substring of a permutation of v_{1}, 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^{2}n) time.. |

2. |
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, 2017.07, 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.. |

3. |
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, 2017.12, 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.. |

4. |
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, 2017.08, 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(z^{2} + 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 z^{2} 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 φ ≤ 2^{o(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.. |

5. |
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, 2017.07, 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.. |

6. |
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, 2017.07, 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.. |

7. |
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, 2017.07, 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.. |

8. |
Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Dynamic Index and LZ Factorization in Compressed Space, The Prague Stringology Conference 2016 (PSC 2016), 2016.08. |

9. |
Hiroe Inoue, Yoshiaki Matsuoka, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Smallest and Largest Repetition Factorizations in O(n log n) Time, The Prague Stringology Conference 2016 (PSC 2016), 2016.08. |

10. |
Yuta Fujishige, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing DAWGs and Minimal Absent Words in Linear Time for Integer Alphabets, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), 2016.08. |

11. |
Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Fully Dynamic Data Structure for LCE Queries in Compressed Space, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), 2016.08. |

12. |
Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Shortest Unique Substring Queries on Run-Length Encoded Strings, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), 2016.08. |

13. |
Yuta Fujishige, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Finding Gapped Palindromes Online, 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), 2016.08. |

14. |
Yoshiaki Matsuoka, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Florin Manea, Factorizing a String into Squares in Linear Time, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), 2016.06. |

15. |
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), 2016.06. |

16. |
Makoto Nishida, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Inferring Strings from Full Abelian Periods, 26th International Symposium on Algorithms and Computation (ISAAC 2015), 2015.12. |

17. |
Yuka Tanimura, Yuta Fujishige, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, A Faster Algorithm for Computing Maximal alpha-gapped Repeats in a String, 22nd International Symposium on String Processing and Information Retrieval (SPIRE 2015), 2015.09. |

18. |
Hideo Bannai, Shunsuke Inenaga, Tomasz Kociumaka, Arnaud Lefebvre, Jakub Radoszewski, Wojciech Rytter, Shiho Sugimoto, Tomasz Walen, Efficient Algorithms for Longest Closed Factor Array, 22nd International Symposium on String Processing and Information Retrieval (SPIRE 2015), 2015.09. |

19. |
Takaaki Nishimoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Left-Right Maximal Generic Words, The Prague Stringology Conference 2015 (PSC 2015), 2015.08. |

20. |
Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski, Simon J. Puglisi, Shiho Sugimoto, iverse Palindromic Factorization Is NP-complete, 19th International Conference on Developments in Language Theory (DLT 2015), 2015.07. |

21. |
Yoshiaki Matsuoka, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Semi-dynamic compact index for short patterns and succinct van Emde Boas tree, 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015), 2015.07. |

22. |
Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding, 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015), 2015.06. |

23. |
Yuya Tamakoshi, Keisuke Goto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, An opportunistic text indexing structure based on run length encoding, 9th International Conference on Algorithms and Complexity (CIAC 2015), 2015.05. |

24. |
Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, Kazuya Tsuruta
, A new characterization of maximal repetitions by Lyndon trees, 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), 2015.01. |

25. |
Keisuke Goto, Hideo Bannai, Space Efficient Linear Time Lempel-Ziv Factorization for Small Alphabets, Data Compression Conference 2014 (DCC 2014), 2014.03. |

26. |
Jun'ichi Yamamoto, Tomohiro I, Hideo Bannai, Masayuki Takeda, Faster Compact On-Line Lempel-Ziv Factorization, 31st Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014.03. |

27. |
Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Shortest Unique Substrings Queries in Optimal Time, 40th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2014), 2014.01. |

28. |
後藤 啓介, Hideo Bannai, 高速かつ省領域な線形時間LZ分解アルゴリズム, 第145回アルゴリズム研究会, 2013.11. |

29. |
Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Faster Lyndon factorization algorithms for SLP and LZ78 compressed text, 20th International Symposium on String Processing and Information Retrieval (SPIRE 2013), 2013.10. |

30. |
Shiho Sugimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Reversed Lempel-Ziv Factorization Online, The Prague Stringology Conference 2013 (PSC 2013), 2013.09. |

31. |
Tomohiro I, Wataru Matsubara, Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Kazuyuki Narisawa, Ayumi Shinohara, Detecting regularities on grammar-compressed strings, 38th International Symposium on Mathematical Foundations of Computer Science (MFCS 2013), 2013.08. |

32. |
Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Efficient Lyndon factorization of grammar compressed text, 24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013), 2013.06. |

33. |
Hideo Bannai, Pawel Gawrychowski, Shunsuke Inenaga and Masayuki Takeda, Converting SLP to LZ78 in almost linear time, 24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013), 2013.06. |

34. |
Toshiya Tanaka, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Computing convolution on grammar-compressed text, Data Compression Conference 2013 (DCC 2013), 2013.03. |

35. |
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), 2013.03. |

36. |
Keisuke Goto and Hideo Bannai, Simpler and Faster Lempel Ziv Factorization, Data Compression Conference 2013 (DCC 2013), 2013.03. |

37. |
Takashi Katsura, Kazuyuki Narisawa, Ayumi Shinohara, Hideo Bannai and Shunsuke Inenaga, Permuted pattern matching on multi-track strings, 38th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2013), 2013.01. |

38. |
Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Efficient LZ78 factorization of grammar compressed text, 19th International Symposium on String Processing and Information Retrieval (SPIRE 2012), 2012.10. |

39. |
Kazuhito Hagio, Takashi Ohgami, Hideo Bannai, Masayuki Takeda, Eager XPath Evaluation over XML Streams, 19th International Symposium on String Processing and Information Retrieval (SPIRE 2012), 2012.10. |

40. |
Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, The position heap of a trie, 19th International Symposium on String Processing and Information Retrieval (SPIRE 2012), 2012.10. |

41. |
Yoko Anan, Kohei Hatano, Hideo Bannai, Masayuki Takeda, and Ken Satoh, Polyphonic Music Classification on Symbolic Data using Dissimilarity Functions, 13th International Society for Music Information Retrieval Conference (ISMIR 2012), 2012.10. |

42. |
Tomohiro I, Yuki Enokuma, Hideo Bannai, and Masayuki Takeda, General Algorithms for Mining Closed Flexible Patterns under Various Equivalence Relations, European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD 2012), 2012.09. |

43. |
Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Speeding up q-gram mining on grammar-based compressed texts, 23rd Annual Symposium on Combinatorial Pattern Matching (CPM 2012), 2012.07. |

44. |
Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Computing q-gram Non-overlapping Frequencies on SLP Compressed Texts, 38th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2012), 2012.01. |

45. |
Yoko Anan, Kohei Hatano, Hideo Bannai, Masayuki Takeda, Music Genre Classification using Similarity Functions, 12th International Society for Music Information Retrieval Conference (ISMIR 2011)
, 2011.10. |

46. |
Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Fast q-gram Mining on SLP Compressed Strings, 18th International Symposium on String Processing and Information Retrieval (SPIRE 2011), 2011.10. |

47. |
Kazuhito Hagio, Takashi Ohgami, Hideo Bannai, Masayuki Takeda, Efficient Eager XPath Filtering over XML Streams, The Prague Stringology Conference 2011 (PSC 2011), 2011.08. |

48. |
Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Inferring Strings from Suffix Trees and Links on a Binary Alphabet, The Prague Stringology Conference 2011 (PSC 2011), 2011.08. |

49. |
Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Longest Common Substring/Subsequence of Non-linear Texts, The Prague Stringology Conference 2011 (PSC 2011), 2011.08. |

50. |
Takanori Yamamoto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Faster Subsequence and Don't-Care Pattern Matching on Compressed Texts, 22nd Annual Symposium on Combinatorial Pattern Matching (CPM 2011), 2011.06. |

51. |
Hideo Bannai, Kohei Hatano, Shunsuke Inenaga, Masayuki Takeda, Practical algorithms for pattern based linear regression, 8th International Conference on Discovery Science (DS'05), 2005.10. |

52. |
Hideo Bannai, Heikki Hyyro, Ayumi Shinohara, Masayuki Takeda, Kenta Nakai, Satoru Miyano, Finding optimal pairs of patterns, 4th Workshop on Algorithms in Bioinformatics (WABI 2004), 2004.09. |

53. |
Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Inferring strings from graphs and arrays, 28th International Symposium on Mathematical Foundations of Computer Science (MFCS2003), 2003.08. |

54. |
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, The 13th International Conference on Genome Informatics, 2002.12. |

55. |
Tomohiro I, Takaaki Nishimoto, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Compressed Automata for Dictionary Matching, 18th International Conference on Implementation and Application of Automata (CIAA 2013),. |