| 大会名称 |
|---|
| 2010年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2010 |
| 発行日 |
| 2010/8/20 |
| セッション番号 |
| 3A |
| セッション名 |
| アルゴリズム・コンピュテーション(1) |
| 講演日 |
| 2010/09/07 |
| 講演場所(会議室等) |
| A会場（総合学習プラザ1F 第5講義室） |
| 講演番号 |
| A-016 |
| タイトル |
| Verifying a Parameterized Border Array in O(n^<1.5>) Time |
| 著者名 |
| 井 智弘, 稲永 峻介, 坂内 英夫, 竹田 正幸, |
| キーワード |
| parameterized pattern matching |
| 抄録 |
| 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(n1.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 ¥frac{1}{e} ¥sum_{k=0}^{¥infty} ¥frac{k^{n}}{k!}, and hence our algorithm is quite efficient. |
| 本文pdf |
| PDF download (223.3KB) |