5 papers
Efficient Dynamic Dictionary Matching with DAWGs and AC-automata
Diptarama Hendrian, Shunsuke Inenaga, Ryo Yoshinaka +1
The dictionary matching is a task to find all occurrences of patterns in a set (called a dictionary) on a text . The Aho-Corasick-automaton (AC-automaton) is a data structur…
New Variants of Pattern Matching with Constants and Variables
Yuki Igarashi, Diptarama, Ryo Yoshinaka +1
Given a text and a pattern over two types of symbols called constants and variables, the parameterized pattern matching problem is to find all occurrences of substrings of the text…
Duel and sweep algorithm for order-preserving pattern matching
Davaajav Jargalsaikhan, Diptarama, Ryo Yoshinaka +1
Given a text and a pattern over alphabet , the classic exact matching problem searches for all occurrences of pattern in text . Unlike exact matching problem, ord…
Position Heaps for Parameterized Strings
Diptarama, Takashi Katsura, Yuhei Otomo +2
We propose a new indexing structure for parameterized strings, called parameterized position heap. Parameterized position heap is applicable for parameterized pattern matching prob…
Longest Common Subsequence in at Least Length Order-Isomorphic Substrings
Yohei Ueki, Diptarama, Masatoshi Kurihara +6
We consider the longest common subsequence (LCS) problem with the restriction that the common subsequence is required to consist of at least length substrings. First, we show a…