Generalized Dictionary Matching Under Substring Consistent Equivalence Relations. Given a set of patterns called a dictionary and a text, the dictionary matching problem is a task to find all occurrence positions of all patterns in the text. The dictionary matching problem can be solved efficiently by using the AhoCorasick algorithm. Recently, Matsuoka et al. TCS, 2016 proposed a generalization of pattern matching problem under substring consistent equivalence relations and presented a generalization of the KnuthMorrisPratt algorithm to solve this problem. An equivalence relation (approx ) is a substring consistent equivalence relation (SCER) if for two strings X, Y, (X approx Y) implies (X  Y) and (Xi:j approx Yi:j) for all (1 le i le j le X). In this paper, we propose a generalization of the dictionary matching problem and present a generalization of the AhoCorasick algorithm for the dictionary matching under SCER. We present an algorithm that constructs SCER automata and an algorithm that performs dictionary matching under SCER by using the automata. Moreover, we show the time and space complexity of our algorithms with respect to the size of input strings.

Cartesian Tree Matching and Indexing We introduce a new metric of match, called Cartesian tree matching, which means that two strings match if they have the same Cartesian trees. Based on Cartesian tree matching, we define single pattern matching for a text of length n and a pattern of length m, and multiple pattern matching for a text of length n and k patterns of total length m. We present an O(nm) time algorithm for single pattern matching, and an O((nm) log k) deterministic time or O(nm) randomized time algorithm for multiple pattern matching. We also define an index data structure called Cartesian suffix tree, and present an O(n) randomized time algorithm to build the Cartesian suffix tree. Our efficient algorithms for Cartesian tree matching use a representation of the Cartesian tree, called the parentdistance representation.