| Presentation | 2012-12-10 Constructing Position Heaps for Various Pattern Matching Yuhei Otomo, Kazuyuki Narisawa, Ayumi Shinohara, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We propose two indexing structures, parameterized position heap and multi-track position heap. The former is applicable for parameterized pattern matching problem, where the pattern P matches a substring t of the text T if there exists a bijective mapping from the symbols of P to the symbols of t. The latter is useful for multi-track string matching, where texts and patterns are tuples of strings, and we try to match a multi-track pattern to a multi-track texts, by allowing the order of pattern tracks to be permuted. We show that both of these position heaps can be constructed in linear time with respect to the text size, and propose pattern matching algorithms using these positioin heaps. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Pattern Matching Problem / Parameterized String / Multi-Track Sting / Position Heap |
| Paper # | COMP2012-44 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2012/12/3(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Constructing Position Heaps for Various Pattern Matching |
| Sub Title (in English) | |
| Keyword(1) | Pattern Matching Problem |
| Keyword(2) | Parameterized String |
| Keyword(3) | Multi-Track Sting |
| Keyword(4) | Position Heap |
| 1st Author's Name | Yuhei Otomo |
| 1st Author's Affiliation | Graduate School of Information Science, Tohoku University() |
| 2nd Author's Name | Kazuyuki Narisawa |
| 2nd Author's Affiliation | Graduate School of Information Science, Tohoku University |
| 3rd Author's Name | Ayumi Shinohara |
| 3rd Author's Affiliation | Graduate School of Information Science, Tohoku University |
| Date | 2012-12-10 |
| Paper # | COMP2012-44 |
| Volume (vol) | vol.112 |
| Number (no) | 340 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |