三重野 琢也
| 情報・ネットワーク工学専攻 | 助教 |
| Ⅰ類（情報系） | 助教 |
研究者情報
経歴
学歴
研究活動情報
論文
- Computing maximal palindromes in non-standard matching models
Takuya Mieno; Mitsuru Funakoshi; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
筆頭著者, Information and Computation, Elsevier BV, 304巻, 掲載ページ 105283-105283, 出版日 2025年05月, 査読付
研究論文（学術雑誌） - Online and Offline Algorithms for Counting Distinct Closed Factors via Sliding Suffix Trees
Takuya Mieno; Shun Takahashi; Kazuhisa Seto; Takashi Horiyama
筆頭著者, 出版日 2025年02月, 査読付
研究論文（国際会議プロシーディングス） - Linear-Time Computation of Generalized Minimal Absent Words for Multiple Strings
Kouta Okabe; Takuya Mieno; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai
String Processing and Information Retrieval, Springer Nature Switzerland, 掲載ページ 331-344, 出版日 2023年09月20日, 査読付
研究論文（国際会議プロシーディングス） - Finding top-k longest palindromes in substrings
Kazuki Mitani; Takuya Mieno; Kazuhisa Seto; Takashi Horiyama
責任著者, Theoretical Computer Science, Elsevier BV, 掲載ページ 114183-114183, 出版日 2023年09月, 査読付
研究論文（学術雑誌） - Data Structures for Computing Unique Palindromes in Static and Non-Static Strings
Takuya Mieno; Mitsuru Funakoshi
筆頭著者, Algorithmica, Springer Science and Business Media LLC, 出版日 2023年08月30日, 査読付
研究論文（学術雑誌） - Computing Palindromes on a Trie in Linear Time
Takuya Mieno; Mitsuru Funakoshi; Shunsuke Inenaga
筆頭著者, 33rd International Symposium on Algorithms and Computation (ISAAC 2022), 248巻, 出版日 2022年12月, 査読付
研究論文（国際会議プロシーディングス） - Online Algorithms for Finding Distinct Substrings with Length and Multiple Prefix and Suffix Conditions
Laurentius Leonard; Shunsuke Inenaga; Hideo Bannai; Takuya Mieno
String Processing and Information Retrieval, Springer International Publishing, 掲載ページ 24-37, 出版日 2022年11月01日, 査読付
研究論文（国際会議プロシーディングス） - Combinatorics of minimal absent words for a sliding window
Tooru Akagi; Yuki Kuhara; Takuya Mieno; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
Theoretical Computer Science, Elsevier BV, 927巻, 掲載ページ 109-119, 出版日 2022年06月, 査読付
研究論文（学術雑誌） - Shortest Unique Palindromic Substring Queries in Semi-dynamic Settings
Takuya Mieno; Mitsuru Funakoshi
筆頭著者, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 13270 LNCS巻, 掲載ページ 425-438, 出版日 2022年05月29日, 査読付
研究論文（国際会議プロシーディングス） - Computing Minimal Unique Substrings for a Sliding Window
Takuya Mieno; Yuta Fujishige; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
筆頭著者, Algorithmica, Springer Science and Business Media LLC, 84巻, 3号, 掲載ページ 670-693, 出版日 2022年03月, 査読付, Abstract
A substring u of a string T is called a minimal unique substring (MUS) of T if u occurs exactly once in T and any proper substring of u occurs at least twice in T. In this paper, we study the problem of computing MUSs for a sliding window over a given string T. We first show how the set of MUSs can change when the window slides over T. We then present an $$O(n\log \sigma ')$$-time and O(d)-space algorithm to compute MUSs for a sliding window of size d over the input string T of length n, where $$\sigma '\le d$$ is the maximum number of distinct characters in every window.
研究論文（学術雑誌） - Palindromic trees for a sliding window and its applications
Takuya Mieno; Kiichi Watanabe; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
筆頭著者, Information Processing Letters, Elsevier BV, 173巻, 掲載ページ 106174-106174, 出版日 2022年01月, 査読付
研究論文（学術雑誌） - String Sanitization Under Edit Distance: Improved and Generalized.
Takuya Mieno; Solon P. Pissis; Leen Stougie; Michelle Sweering
筆頭著者, 32nd Annual Symposium on Combinatorial Pattern Matching(CPM), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 掲載ページ 19-18, 出版日 2021年06月, 査読付
研究論文（国際会議プロシーディングス） - Space-efficient algorithms for computing minimal/shortest unique substrings
Takuya Mieno; Dominik Köppl; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
筆頭著者, Theoretical Computer Science, Elsevier BV, 845巻, 掲載ページ 230-242, 出版日 2020年12月, 査読付
研究論文（学術雑誌）, 英語 - Minimal Unique Substrings and Minimal Absent Words in a Sliding Window
Takuya Mieno; Yuki Kuhara; Tooru Akagi; Yuta Fujishige; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
筆頭著者, SOFSEM 2020: Theory and Practice of Computer Science, Springer International Publishing, 掲載ページ 148-160, 出版日 2020年, 査読付
論文集(書籍)内論文 - Algorithms and combinatorial properties on shortest unique palindromic substrings
Hiroe Inoue; Yuto Nakashima; Takuya Mieno; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
Journal of Discrete Algorithms, Elsevier BV, 52-53巻, 掲載ページ 122-132, 出版日 2018年09月, 査読付
研究論文（学術雑誌）, 英語 - Tight Bounds on the Maximum Number of Shortest Unique Substrings.
Takuya Mieno; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
筆頭著者, 28th Annual Symposium on Combinatorial Pattern Matching(CPM), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 掲載ページ 24-11, 出版日 2017年, 査読付
研究論文（国際会議プロシーディングス） - Shortest unique substring queries on run-length encoded strings
Takuya Mieno; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
筆頭著者, Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 58巻, 出版日 2016年08月01日, 査読付
研究論文（国際会議プロシーディングス）, 英語
共同研究・競争的資金等の研究課題
- 不在/稀少文字列の計算技法と一般化文字列への展開
三重野 琢也
日本学術振興会, 科学研究費助成事業, 電気通信大学, 若手研究, 24K20734
研究期間 2024年04月 - 2027年03月 - 文字列処理におけるNP困難問題の高速解法の追求
三重野 琢也
日本学術振興会, 科学研究費助成事業 学術変革領域研究(A), 電気通信大学, 学術変革領域研究(A), 23H04381
研究期間 2023年04月01日 - 2025年03月31日 - 動的文字列処理に対するアルゴリズム技法の開発と計算限界の解明
三重野 琢也
日本学術振興会, 科学研究費助成事業 研究活動スタート支援, 電気通信大学, 研究活動スタート支援, 22K21273
研究期間 2022年08月31日 - 2024年03月31日 - 最先端文字列アルゴリズム理論に基づく巨大データ解析技法
三重野 琢也
日本学術振興会, 科学研究費助成事業 特別研究員奨励費, 九州大学, 特別研究員奨励費, 前から読んでも後ろから読んでも同じ文字列を回文という。文字列から回文構造を発見する問題は特に生物情報科学の分野で重要視され、盛んに研究されている。 本研究期間においては、文字列中の回文構造を効率よく検出するためのデータ構造・アルゴリズムの開発を主として行った。他にも文字列圧縮アルゴリズムの性能に関する研究などを行い、以下の６つの成果を得た。 １つ目の成果は、入力文字列に対して特定の編集操作が許された設定において、ユニーク回文部分文字列を計算するアルゴリズムの提案である。ユニーク回文部分文字列とは、文字列中にちょうど一度だけ出現する回文である。本成果は国際会議 SPIRE 2021 に採択されており、さらにその結果を応用した研究成果は国際会議 IWOCA 2022 に投稿された。 ２つ目の成果は、双方向マクロスキームと呼ばれる文字列圧縮形式に対する圧縮性能限界の解明である。３つ目の成果は、LZEnd 圧縮と呼ばれる文字列圧縮手法の圧縮性能に関する新たな結果の証明である。文字列圧縮手法の性能を比較・解析する研究は文字列圧縮研究の分野で近年盛んに行われており、特に２つ目の成果は同分野で注目されていた未解決問題のひとつを解決したものである。２つ目と３つ目の成果は国際会議 SPIRE 2021 に採択されている。 ４つ目の成果は、RePair という文字列圧縮手法の圧縮性能に関する新たな結果の証明である。５つ目の成果は、デカルト木部分列照合問題と呼ばれる緩和された部分列照合問題に対するアルゴリズムの提案である。６つ目の成果は、圧縮表現された文字列上で、その文字列中に存在しない不在文字列を計算するアルゴリズムの提案である。上記３つの成果はいずれも国際会議 CPM 2022 に採択されている。, 20J11983
研究期間 2020年04月24日 - 2022年03月31日
