publications

Journal Papers

1. Tooru Akagi, Yuki Kuhara, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda. Combinatorics of minimal absent words for a sliding window. Theoretical Computer Science, Vol. 927, pp. 109-119 (2022).
2. Katsuhito Nakashima, Noriki Fujisato, Diptarama Hendrian, Yuto Nakashima, Ryo Yoshinaka, Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, and Masayuki Takeda. Parameterized DAWGs: Efficient constructions and bidirectional pattern searches. Theoretical Computer Science, Vol. 933, pp. 21-42 (2022).
3. Hiroe Inoue, Yoshiaki Matsuoka, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Factorizing strings into repetitions. Theory of Computing Systems, Vol. 66, pp. 484-501 (2022).
4. Takuya Mieno, Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Palindromic trees for a sliding window and its applications. Information Processing Letters, Vol. 173, 106174 (2022).
5. Takuya Mieno, Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Minimal Unique Substrings for a Sliding Window. Algotithmica (2021)
6. Ryo Sugahara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Efficiently computing runs on a trie. Theoretical Computer Science, Vol. 887, pp. 143-151 (2021).
7. Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda. c-trie++: A dynamic trie tailored for fast prefix searches. Information and Computation, Vol. 285, 104794 (2021).
8. Shiori Mitsuya, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Compressed Communication Complexity of Hamming Distance. Algorithms, Vol. 14 (4), Article No. 116 (2021).
9. Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Computing longest palindromic substring after single-character or block-wise edits. Theoretical Computer Science, Vol. 859, pp. 116-133 (2021).
10. Takuya Mieno, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Space-efficient algorithms for computing minimal/shortest unique substrings. Theoretical Computer Science, Vol. 845, pp. 230-242 (2020).
11. Kazuya Tsuruta, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Grammar-compressed Self-index with Lyndon Words. IPSJ Transactions on Mathematical Modeling and Its Applications (TOM), Vol. 13, No. 2, pp. 84-92 (2020).
12. Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Fast Algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded Strings. Theory of Computing Systems, vol. 64, pp. 1273–1291 (2020).
13. Isamu Furuya, Takuya Takagi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Takuya Kida. Practical Grammar Based on Maximal Repeats. Algorithms, Vol. 13 (4), Article No. 103 (2020).
14. Yuto Nakashima, Takuya Takagi, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. On the Size of the Smallest Alphabet for Lyndon Trees. Theoretical Computer Science, Vol 792, pp. 131-143 (2019).
15. Hiroe Inoue, Yuto Nakashima, Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Algorithms and combinatorial properties on shortest unique palindromic substrings. Journal of Discrete Algorithms, Vol. 52-53, pp. 122-132 (2018).
16. Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, and Kazuya Tsuruta. The "Runs" Theorem. SIAM Journal on Computing, Vol. 46 (5) 1501-1514 (2017).
17. Yuto Nakashima, Takashi Okabe, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Inferring Strings from Lyndon Factorization. Theoretical Computer Science 689, pp. 147-156 (2017).
18. Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Faster Lyndon factorization algorithms for SLP and LZ78 compressed text. Theoretical Computer Science 656, part B:215-224 (2016).
19. Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Constructing LZ78 tries and position heaps in linear time for large alphabets. Information Processing Letters 115(9):655-659 (2015).

Reviewed Conference Papers

1. Taketo Tsujimoto, Hiroki Shibata, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga. Computing Longest Common Subsequence under Cartesian-Tree Matching Model. Proc. of the 35th International Workshop on Combinatorial Algorithms (IWOCA 2024).
2. Mitsuru Funakoshi, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda. Computing maximal palindromes in non-standard matching models. Proc. of the 35th International Workshop on Combinatorial Algorithms (IWOCA 2024).
3. Kouta Okabe, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai. Linear-Time Computation of Generalized Minimal Absent Words for Multiple Strings. Proc. of 30th International Symposium on String Processing and Information Retrieval (SPIRE 2023), Lecture Notes in Computer Science, Vol. 14240, pp. 331-344 (2023).
4. Kaisei Kishi, Yuto Nakashima, Shunsuke Inenaga. Largest Repetition Factorization of Fibonacci Words. Proc. of 30th International Symposium on String Processing and Information Retrieval (SPIRE 2023), Lecture Notes in Computer Science, Vol. 14240, pp. 284-296 (2023).
5. Hiroki Arimura, Shunsuke Inenaga, Yasuaki Kobayashi, Yuto Nakashima, Mizuki Sue. Optimally Computing Compressed Indexing Arrays Based on the Compact Directed Acyclic Word Graph. Proc. of 30th International Symposium on String Processing and Information Retrieval (SPIRE 2023), Lecture Notes in Computer Science, Vol. 14240, pp. 28-34 (2023).
6. Yuki Yonemoto, Yuto Nakashima, Shunsuke Inenaga. Computing SEQ-IC-LCS of Labeled Graphs. Proc. of the Prague Stringology Conference 2023 (PSC 2023), pp. 3-17 (2023).
7. Hideo Bannai, Mitsuru Funakoshi, Kazuhiro Kurita, Yuto Nakashima, Kazuhisa Seto, Takeaki Uno. Optimal LZ-End Parsing is Hard. Proceedings of the 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023), LIPIcs, Vol. 259, pp. 3:1-3:11 (2023).
8. Hiroto Fujimaru, Yuto Nakashima, Shunsuke Inenaga. On Sensitivity of Compact Directed Acyclic Word Graphs. Proceedings of 14th International Conference on Words (WORDS 2023), Lecture Notes in Computer Science, Vol. 13899, pp. 168-180 (2023).
9. Yuuki Yonemoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai. Space-Efficient STR-IC-LCS Computation. In Proceedings of 47th International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 2023), Lecture Notes in Computer Science, Vol. 13878, pp. 372-384 (2023).
10. Tooru Akagi, Kouta Okabe, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga. Minimal Absent Words on Run-Length Encoded Strings. Proceedings of the 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022), LIPIcs, Vol. 223, pp. 27:1-27:17 (2022).
11. Kosuke Fujita, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda. Longest Common Rollercoasters. Proc. of 28th International Symposium on String Processing and Information Retrieval (SPIRE 2021), Lecture Notes in Computer Science, Vol. 12944, pp. 21-32 (2021).
12. Tooru Akagi, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda. Grammar Index By Induced Suffix Sorting. Proc. of 28th International Symposium on String Processing and Information Retrieval (SPIRE 2021), Lecture Notes in Computer Science, Vol. 12944, pp. 85-99 (2021).
13. Akio Nishimoto, Noriki. Fujisato, Yuto Nakashima, Shunsuke Inenaga. Position Heaps for Cartesian-tree Matching on Strings and Tries. Proc. of 28th International Symposium on String Processing and Information Retrieval (SPIRE 2021), Lecture Notes in Computer Science, Vol. 12944, pp. 241-254 (2021).
14. Takumi Ideue, Takuya Mieno, Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Masayuki Takeda. On the approximation ratio of LZ-End to LZ77. Proc. of 28th International Symposium on String Processing and Information Retrieval (SPIRE 2021), Lecture Notes in Computer Science, Vol. 12944, pp. 114-126 (2021).
15. Ryo Hirakawa, Yuto Nakashima, Shunsuke Inenaga, Masayuki Takeda. Counting Lyndon Subsequence. Proc. of the Prague Stringology Conference 2021 (PSC 2021), pp. 53-60 (2021).
16. Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. The Parameterized Suffix Tray. In Proceedings of 12th International Conference on Algorithms and Complexity (CIAC 2021), Lecture Notes in Computer Science, Vol. 12701, pp. 258-270 (2021).
17. Kanaru Kutsukake, Takuya Matsumoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. On repetitiveness measures of Thue-Morse words. In Proceedings of 27th International Symposium on String Processing and Information Retrieval (SPIRE 2020), Lecture Notes in Computer Science, Vol. 12303, pp. 213-220 (2020).
  received Best Paper Award.
18. Akihiro Nishi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Towards Efficient Interactive Computation of Dynamic Time Warping Distance. In Proceedings of 27th International Symposium on String Processing and Information Retrieval (SPIRE 2020), Lecture Notes in Computer Science, Vol. 12303, pp. 27-41 (2020).
19. Hideo Bannai, Takuya Mieno, Yuto Nakashima. Lyndon Words, the Three Squares Lemma, and Primitive Squares. In Proceedings of 27th International Symposium on String Processing and Information Retrieval (SPIRE 2020), Lecture Notes in Computer Science, Vol. 12303, pp. 265-273 (2020).
20. Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, and Ayumi Shinohara. Detecting k-(Sub-)Cadences and Equidistant Subsequence Occurrences. In Proceedings of the 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020), LIPIcs, Vol. 161, pp. 12:1-12:11 (2020).
21. Katsuhito Nakashima, Noriki Fujisato, Diptarama Hendrian, Yuto Nakashima, Ryo Yoshinaka, Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, and Masayuki Takeda. DAWGs for Parameterized Matching: Online Construction and Related Indexing Structures. In Proceedings of the 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020), LIPIcs, Vol. 161, pp. 26:1-26:14 (2020).
22. Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. c-trie++: Dynamic Trie Tailored for Fast Prefix Searches. In Proceedings of Data Compression Conference 2020, pp. 243-252 (2020).
23. Kohei Yamada, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Faster STR-EC-LCS Computation. In Proceedings of 46th International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 2020), Lecture Notes in Computer Science, Vol. 12011, pp. 125-135 (2020).
24. Takuya Mieno, Yuki Kuhara, Tooru Akagi, Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Minimal Unique Substrings and Minimal Absent Words in a Sliding Window. In Proceedings of 46th International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 2020), Lecture Notes in Computer Science, Vol. 12011, pp. 148-160 (2020).
25. Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. An Improved Data Structure for Left-Right Maximal Generic Words Problem. In Proceedings of the 30th International Symposium on Algorithms and Computation (ISAAC 2019), LIPIcs 149, 40:1--40:12 (2019).
26. Takuya Mieno, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Compact Data Structure for Shortest Unique Substring Queries. In Proceedings of 26th International Symposium on String Processing and Information Retrieval (SPIRE 2019), Lecture Notes in Computer Science, Vol. 11811, pp. 107-123 (2019).
27. Kazuki Kai, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, and Tomasz Kociumaka. On Longest Common Property Preserved Substring Queries. In Proceedings of 26th International Symposium on String Processing and Information Retrieval (SPIRE 2019), Lecture Notes in Computer Science, Vol. 11811, pp. 162-174 (2019).
28. Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets. In Proceedings of 26th International Symposium on String Processing and Information Retrieval (SPIRE 2019), Lecture Notes in Computer Science, Vol. 11811, pp. 382-391 (2019).
29. Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Computing Maximal Palindromes and Distinct Palindromes in a Trie. In Proceedings of the Prague Stringology Conference 2019 (PSC 2019), pp. 3-15 (2019).
30. Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Shortest Unique Palindromic Substring Queries on Run-Length Encoded Strings. In Proceedings of the 30th International Workshop on Combinatorial Algorithms (IWOCA 2019), LNCS 11638, pp. 430-441 (2019).
31. Ryo Sugahara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Computing runs on a trie. In Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), LIPIcs, Vol 128, pp. 23:1-23-11 (2019).
32. Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. On the Size of Overlapping Lempel-Ziv and Lyndon Factorizations. In Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), LIPIcs, Vol 128, pp. 29:1-29-11 (2019).
33. Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Faster queries for longest substring palindrome after block edit. In Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), LIPIcs, Vol 128, pp. 27:1-27-13 (2019).
34. Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. The Parameterized Position Heap of a Trie. In Proceedings of 11th International Conference on Algorithms and Complexity (CIAC 2019), Lecture Notes in Computer Science, Vol. 11485, pp. 237-248 (2019).
35. Isamu Furuya, Takuya Takagi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Takuya Kida. MR-RePair: Grammar Compression based on Maximal Repeats. In Proceedings of the Data Compression Conference 2019 (DCC 2019), pp. 508-517 (2019).
36. Yuki Kuhara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Recovering, counting and enumerating strings from forward and backward suffix arrays. In Proceedings of the 25th International Symposium on String Processing and Information Retrieval (SPIRE 2018), LNCS 11147 : 254-267 (2018).
37. Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Right-to-left online construction of parameterized position heaps. In Proceedings of the Prague Stringology Conference 2018 (PSC 2018), pp. 91-102 (2018).
38. Akihiro Nishi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. O(n log n)-time text compression by LZ-style longest first substitution. In Proceedings of the Prague Stringology Conference 2018 (PSC 2018), pp. 12-26 (2018).
39. Kotaro Aoyama, Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Faster Online Elastic Degenerate String Matching. In Proceedings of the 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018), LIPICS Vol.105, 9:1--9:10 (2018).
40. Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Longest substring palindrome after edit. In Proceedings of the 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018), LIPICS Vol.105, 12:1--12:14 (2018).
41. Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Longest Lyndon Substring After Edit. In Proceedings of the 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018), LIPICS Vol.105, 19:1--19:10 (2018).
42. Isamu Furuya, Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Lyndon Factorization of Grammar Compressed Texts Revisited. In Proceedings of the 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018), LIPICS Vol.105, 24:1--24:10 (2018).
43. Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Almost linear time computation of maximal repetitions in run length encoded strings. In Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017), LIPICS Vol.92, 33:1--33:12 (2017).
44. Yuto Nakashima, Takuya Takagi, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. On Reverse Engineering the Lyndon Tree. In Proceedings of the Prague Stringology Conference 2017 (PSC 2017), pp. 108-117 (2017).
45. Yuto Nakashima, Hiroe Inoue, Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Shortest Unique Palindromic Substring Queries in Optimal Time. In Proceedings of the 28th International Workshop on Combinatorial Algorithms (IWOCA 2017), LNCS 10765:397-408 (2018).
46. Juha Kärkkäinen, Dominik Kempa, Yuto Nakashima, Simon J. Puglisi, and Arseny M. Shur. On the Size of Lempel-Ziv and Lyndon Factorizations. In Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), LIPIcs 66, 45:1--45:13 (2017).
47. Golnaz Badkobeh, Travis Gagie, Szymon Grabowski, Yuto Nakashima, Simon J. Puglisi, and Shiho Sugimoto. Longest Common Abelian Factors and Large Alphabets. In Proceedings of the 23rd International Symposium on String Processing and Information Retrieval (SPIRE 2016), LNCS 9954:254-259 (2016).
48. Hiroe Inoue, Yoshiaki Matsuoka, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Computing Smallest and Largest Repetition Factorizations in O(n log n) time. In Proceedings of the Prague Stringology Conference 2016 (PSC 2016), pp. 135-145 (2016).
49. Takaaki Nishimoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Computing Left-Right Maximal Generic Words. In Proceedings of the Prague Stringology Conference 2015 (PSC 2015), pp. 5-16 (2015).
50. Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, and Kazuya Tsuruta. A New Characterization of Maximal Repetitions by Lyndon Trees. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pp. 562-571 (2015).
51. Yuto Nakashima, Takashi Okabe, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Inferring Strings from Lyndon Factorization. In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014), LNCS 8635:565-576 (2014).
52. Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Faster Lyndon factorization algorithms for SLP and LZ78 compressed text. In Proceedings of the 20th International Symposium on String Processing and Information Retrieval (SPIRE 2013), LNCS 8214:174-185 (2013).
53. Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Efficient Lyndon Factorization of Grammar Compressed Text. In Proceedings of the 24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013), LNCS 7922:153-164, (2013).
54. Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. The position heap of a trie. In Proceedings of the 19th International Symposium on String Processing and Information Retrieval (SPIRE 2012), LNCS 7608:360-371 (2012).