@techreport{oai:ipsj.ixsq.nii.ac.jp:00216131,
 author = {大泉, 翼 and 有村, 博紀 and Tsubasa, Oizumi and Hiroki, Arimura},
 issue = {3},
 month = {Jan},
 note = {デカルト木照合（Cartesian tree matching）は，値の大小関係に基づいてテキストの連続な部分文字列とパターンの照合を行う近似照合問題の一種であり，2019 年に Park と, Amir, Landau, Park らによって提案された．本研究では，デカルト木照合問題をテキストの非連続な部分系列に拡張して，デカルト木部分列照合問題を提案する．さらに，この問題を O(mn log n) 時間と O(mn) 領域で解く効率の良いアルゴリズムを与える．このアルゴリズムは，動的計画法と区間最小値クエリを組み合わせることで，先行研究の加井らによるアルゴリズムの時間計算量 O(mn3) を大幅に改善している．, Park, Amir, Landau, and Park proposed in 2019 an approximate matching problem for numerical sequences, called the Cartesian tree matching problem, that asks to find a consecutive substring of a text string that matches a pattern string based on their Cartesian trees. In this paper, we study an extension of the Cartesian tree matching problem from consecutive substrings to non-consecutive subsequences, called the Cartesian tree subsequence matching problem. Then, we present an efficient dynamic programming algorithm that runs in O(mn log n) time and O(mn) space, which improves on the previous O(mn3) time and space algorithm by Kai et al.},
 title = {デカルト木部分列照合問題の高速なアルゴリズム},
 year = {2022}
}