Generalized pattern matching and periodicity under substring consistent equivalence relations
| Autor: | Takahiro Aoki, Masayuki Takeda, Yoshiaki Matsuoka, Hideo Bannai, Shunsuke Inenaga |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
Lemma (mathematics) General Computer Science Efficient algorithm 010102 general mathematics Parameterized complexity 0102 computer and information sciences String searching algorithm 01 natural sciences Substring Theoretical Computer Science Combinatorics 010201 computation theory & mathematics Equivalence relation Pattern matching 0101 mathematics Mathematics |
| Zdroj: | Theoretical Computer Science. 656:225-233 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2016.02.017 |
| Popis: | Let ź be a substring consistent equivalence relation (SCER) on strings such that for any two strings x , y , x ź y implies that (1) | x | = | y | and (2) x i . . j ź y i . . j for all 0 ź i ź j < | x | . Examples of SCER are parameterized pattern matching and order-preserving pattern matching. We present a generalized and efficient algorithm for pattern matching with SCER ź. Also, we show analogues of Fine and Wilf's periodicity lemma hold for SCER. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect