Noriki Fujisato

activity

20182021

collaborators

5 papers

cs.DS2021

Position Heaps for Cartesian-tree Matching on Strings and Tries

Akio Nishimoto, Noriki Fujisato, Yuto Nakashima +1

The Cartesian-tree pattern matching is a recently introduced scheme of pattern matching that detects fragments in a sequential data stream which have a similar structure as a query…

cs.DS2020

The Parameterized Suffix Tray

Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga +2

Let $Σ$ and $Π$ be disjoint alphabets, respectively called the static alphabet and the parameterized alphabet. Two strings $x$ and $y$ over $Σ \cup Π$ of equal length are said to pa…

cs.DS2019

Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets

Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga +2

We present the first worst-case linear time algorithm that directly computes the parameterized suffix and LCP arrays for constant sized alphabets. Previous algorithms either requir…

cs.DS2019

The Parameterized Position Heap of a Trie

Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga +2

Let $Σ$ and $Π$ be disjoint alphabets of respective size $σ$ and $π$ . Two strings over $Σ \cup Π$ of equal length are said to parameterized match (p-match) if there is a bijection $…

cs.DS2018

Right-to-left online construction of parameterized position heaps

Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga +2

Two strings of equal length are said to parameterized match if there is a bijection that maps the characters of one string to those of the other string, so that two strings become…