動的文字列処理に対するアルゴリズム技法の開発と計算限界の解明

本研究は、動的に変化する文字列データを効率的に処理するのためのアルゴリズム技法を開発すること、およびそれに資する文字列構造の数理的性質を解明することが目的である。文字列中にちょうど一度だけ出現する部分文字列をユニーク部分文字列と呼ぶ。今年度は、動的に変化する文字列におけるユニーク部分文字列の変化に関する研究を主として行った。まず、ユニーク部分文字列でありかつ回文構造でもある、ユニーク回文部分文字列に着目をした。そして、文字列中の任意の一文字を別の文字に置換したときのユニーク回文部分文字列の変化についての研究に取り組み、組合せ的性質に関する新たな知見を発見し、それに基づく効率的な文字列処理アルゴリズムを開発した。得られた成果を論文にまとめ、国際論文誌 Algorithmica へ投稿した。なお、投稿した論文の査読結果は年度末時点で未達である。さらに、回文部分文字列の研究に関連して、動的文字列上での最長回文計算のために利用できる部分問題の高速解法の探求および一般化に取り組んだ。このテーマについては、既存結果からの改善と、一般化した問題の定式化および効率的な解法の開発をすでに実施しており、現在はその成果を国際論文誌 Theoretical Computer Science へ投稿する準備を行っている。次年度の序盤に、まずこちらの論文投稿作業を完了させる予定である。また、12月にソウル（韓国）で開催された国際会議 ISAAC 2022 へ参加し、計算機科学分野全般の最新動向や各種アルゴリズム技術に関する情報収集を実施した。

本研究は、動的に変化する文字列データを効率的に処理するのためのアルゴリズム技法を開発すること、およびそれに資する文字列構造の数理的性質を解明することが目的である。文字列中にちょうど一度だけ出現する部分文字列をユニーク部分文字列と呼ぶ。今年度は、動的に変化する文字列におけるユニーク部分文字列の変化に関する研究を主として行った。まず、ユニーク部分文字列でありかつ回文構造でもある、ユニーク回文部分文字列に着目をした。そして、文字列中の任意の一文字を別の文字に置換したときのユニーク回文部分文字列の変化についての研究に取り組み、組合せ的性質に関する新たな知見を発見し、それに基づく効率的な文字列処理アルゴリズムを開発した。得られた成果を論文にまとめ、国際論文誌 Algorithmica へ投稿した。なお、投稿した論文の査読結果は年度末時点で未達である。さらに、回文部分文字列の研究に関連して、動的文字列上での最長回文計算のために利用できる部分問題の高速解法の探求および一般化に取り組んだ。このテーマについては、既存結果からの改善と、一般化した問題の定式化および効率的な解法の開発をすでに実施しており、現在はその成果を国際論文誌 Theoretical Computer Science へ投稿する準備を行っている。次年度の序盤に、まずこちらの論文投稿作業を完了させる予定である。また、12月にソウル（韓国）で開催された国際会議 ISAAC 2022 へ参加し、計算機科学分野全般の最新動向や各種アルゴリズム技術に関する情報収集を実施した。