WEKO3
アイテム
接尾辞木にもとづく部分文字列の数え上げ法
https://ipsj.ixsq.nii.ac.jp/records/210287
https://ipsj.ixsq.nii.ac.jp/records/210287fdba534b-fe1f-461f-8620-e47585c3dff0
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL21182006.pdf (1.0 MB)
|
Copyright (c) 2021 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2021-03-10 | |||||||||
| タイトル | ||||||||||
| タイトル | 接尾辞木にもとづく部分文字列の数え上げ法 | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | A Suffix Tree-Based Algorithm for Counting Substrings | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||
| 資源タイプ | technical report | |||||||||
| 著者所属 | ||||||||||
| 神奈川大学理学部情報科学科 | ||||||||||
| 著者所属 | ||||||||||
| 神奈川大学理学部情報科学科 | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Department of Information Sciences, Faculty of Science, Kanagawa University | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Department of Information Sciences, Faculty of Science, Kanagawa University | ||||||||||
| 著者名 |
ローレンシウス, レオナード
× ローレンシウス, レオナード
× 田中, 賢
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 文字列を取り扱う様々な問題を効率よく解くためのアルゴリズムとデータ構造の研究は古くから研究されており，それらは計算機科学の分野のみならず，計算分子生物学などの分野で応用されている．本稿では接尾辞木というデータ構造を利用し，ある文字列に対し，指定された接頭辞と接尾辞を持つような相異なる部分文字列の個数を求めるという問題を線形時間と線形メモリで解くアルゴリズムを提案する． | |||||||||
| 論文抄録(英) | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 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. | |||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AN1009593X | |||||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2021-AL-182, 号 6, p. 1-8, 発行日 2021-03-10 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 2188-8566 | |||||||||
| Notice | ||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
