文献

J-GLOBAL ID：201702230658128596   整理番号：17A1625832

ストリングにおける最大近似ランの位置付け【Powered by NICT】

Locating maximal approximate runs in a string

著者 (6件)： Amit Mika (Department of Computer Science, University of Haifa, Mount Carmel, Haifa, Israel) ,  Crochemore Maxime (King’s College London, Strand, London WC2R 2LS, UK) ,  Crochemore Maxime (Universite Paris-Est, Institut Gaspard-Monge, 77454 Marne-la-Vallee Cedex 2, France) ,  Landau Gad M. (Department of Computer Science, University of Haifa, Mount Carmel, Haifa, Israel) ,  Landau Gad M. (Department of Computer Science and Engineering, NYU Polytechnic School of Engineering, New York University, Brooklyn, NY, USA) ,  Sokol Dina (Department of Computer and Information Science, Brooklyn College of the City University of New York, Brooklyn, NY, USA)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 700  ページ： 45-62  発行年： 2017年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： ストリングTの正確な実行はそれのプレフィックス続いて恐らくより小さい部分文字列の繰り返しであることをTの空でない文字列である。ストリングにおける最大完全ランを見出すことは,重要な問題があり,それゆえstringologyの分野でよく研究されている一つである。長さnの与えられたストリングTでは,ストリングにおけるすべての最大正確な実行を見出す整数アルファベットに関する一般的順序付きアルファベットまたはO(n)時間上のO(n logn)時間で行うことができる。本論文では,最大近似ラン問題:与えられたストリングTと数K,T’の高々k文字を変え最大完全実行にそれらを変換することをこのようなTの空でない部分文字列T′を見出すを調べた。はこの問題を解決するためにO(n K~2log~2K+O C C)アルゴリズムを提案した,occを見出し部分文字列の数であった。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： アルゴリズム ,  *近似法 ,  文字列
準シソーラス用語： プレフィックス , 【Automatic Indexing@JST】

著者キーワード (5件)： ストリング上のアルゴリズム ,  パターンマッチング ,  反復 ,  タンデム反復配列 ,  実行

分類 (2件)： 計算理論  (JB02000A) ,  記号処理  (JE03000Q)

タイトルに関連する用語 (1件)： 近似