2024-03-28T20:47:08Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:002102872023-04-27T10:00:04Z01164:02592:10486:10558
接尾辞木にもとづく部分文字列の数え上げ法A Suffix Tree-Based Algorithm for Counting Substringsjpnhttp://id.nii.ac.jp/1001/00210185/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=210287&item_no=1&attribute_id=1&file_no=1Copyright (c) 2021 by the Information Processing Society of Japan神奈川大学理学部情報科学科神奈川大学理学部情報科学科ローレンシウス, レオナード田中, 賢文字列を取り扱う様々な問題を効率よく解くためのアルゴリズムとデータ構造の研究は古くから研究されており,それらは計算機科学の分野のみならず,計算分子生物学などの分野で応用されている.本稿では接尾辞木というデータ構造を利用し,ある文字列に対し,指定された接頭辞と接尾辞を持つような相異なる部分文字列の個数を求めるという問題を線形時間と線形メモリで解くアルゴリズムを提案する.Algorithms to solve various problems regarding string processing has long been a topic of research interest. Their applications extend beyond the field of computer science, into other fields such as computational molecular biology. In this paper, by making use of the suffix tree, we propose a linear-time, linear-memory algorithm for the following problem: Given three strings T, P and S, count all the unique substrings of T that has P as its prefix and S as its suffix.AN1009593X研究報告アルゴリズム(AL)2021-AL-1826182021-03-102188-85662021-03-08