A-016 Verifying a Parameterized Border Array in O(n^<1.5>) Time
スポンサーリンク
概要
- 論文の詳細を見る
The parameterized pattern matching problem is to check if there exists a renaming bijection on the alphabet with which a given pattern can be transformed into a substring of a given text. A parameterized border array (p-border array) is a parameterized version of a standard border array, and we can efficiently solve the parameterized pattern matching problem using p-border arrays. In this paper we present an O(n^<1.5>)-time O(n)-space algorithm to verify if a given integer array of length n is a valid p-border array for an unbounded alphabet. The best previously known solution takes time proportional to the n-th Bell number 1/eΣ^∞_<k=0> k^n/k!, and hence our algorithm is quite efficient.
- FIT(電子情報通信学会・情報処理学会)推進委員会の論文
- 2010-08-20
著者
-
竹田 正幸
九州大学大学院システム情報科学研究院
-
稲永 峻介
九大
-
竹田 正幸
九州大学大学院システム情報科学研究院情報学部門
-
坂内 英夫
九大
-
竹田 正幸
九大
-
井 智弘
九大
-
井 智弘
九州大学大学院システム情報科学府情報学専攻
関連論文
- オンラインランク統合問題 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 楽曲の分類と文字列間の類似性指標について (特集 「脳科学と知識処理」および一般)
- 『恵慶法師集』比良歌群試注
- 国文学の研究教育における機械学習応用(機械学習の科学研究への応用)
- 最大エントロピー原理に基づくオンライン学習 (理論計算機科学の深化と応用)
- 非定常な木情報源に対応する文脈木重みづけ法に関する研究
- Online Learning of Approximate Maximum $p$-Norm Margin Classifiers with Bias (Foundations of Theoretical Computer Science : For New Computational View)
- 漸増的なパストライ構築に基づく高速・軽量XML文書フィルタリング(夏のデータベースワークショップ2007(データ工学,一般))
- 漸増的なパストライ構築に基づく高速・軽量XML文書フィルタリング(テキスト検索,夏のデータベースワークショップ2007(データ工学,一般))
- 定数項の大きな線形しきい値関数に対する高速なオンライン学習(計算機科学の理論とその応用)
- 接尾辞配列による効率的な文字列上の同値類計算
- SVMによるバイパータイトランキング学習を用いたコンピュータ将棋における評価関数の学習(IBIS2010(情報論的学習理論ワークショップ))
- F-036 Online Rank Aggregation
- 2.情報爆発時代のための新しい超高速アルゴリズム(パートI:情報爆発時代における新しい基盤技術,情報爆発時代におけるわくわくするITの創出を目指して)
- F-037 Sparse Substring Pattern Set Discovery using Linear Programming Boosting
- A-016 Verifying a Parameterized Border Array in O(n^) Time
- 圧縮文字列上での $q$-gram 頻度の高速な計算方法 (計算機科学とアルゴリズムの数理的基礎とその応用)
- 確率的評価値をもつゲーム木における最善手探索 (計算機科学とアルゴリズムの数理的基礎とその応用)
- DS-1-10 文字列パターン上の同値関係と飽和パターンの列挙(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- Practical Algorithms for Pattern Based Linear Regression (テーマ:特集「シンボルグラウンディング問題」および一般)
- 類似性指標を用いた楽曲のジャンル分類 (「メディアとAI」および一般)
- 非線形コラージュシステムにおける文字列パターン照合
- 非線形テキストにおける最長共通部分文字列・部分列アルゴリズム
- 非定常な木情報源に対応する文脈木重みづけ法に関する研究
- 類似度に基づくポリフォニックな楽曲の分類
- SVMによる2部ランキング学習を用いたコンピュータ将棋における評価関数の学習(情報・システム基礎)