Faster STRECLCS Computation The longest common subsequence (LCS) problem is a central problem in stringology that finds the longest common subsequence of given two strings A and B. More recently, a set of four constrained LCS problems (called generalized constrained LCS problem) were proposed by Chen and Chao J. Comb. Optim, 2011. In this paper, we consider the substringexcluding constrained LCS (STRECLCS) problem. A string Z is said to be an STRECLCS of two given strings A and B excluding P if, Z is one of the longest common subsequences of A and B that does not contain P as a substring. Wang et al. proposed a dynamic programming solution which computes an STRECLCS in O(mnr) time and space where m  A, n  B, r  P Inf. Process. Lett., 2013. In this paper, we show a new solution for the STRECLCS problem. Our algorithm computes an STRECLCS in O(nSigma  (L1)(mL1)r) time where Sigma leq minm, n denotes the set of distinct characters occurring in both A and B, and L is the length of the STRECLCS. This algorithm is faster than the O(mnr)time algorithm for shortlong STRECLCS (namely, L in O(1) or mL in O(1)), and is at least as efficient as the O(mnr)time algorithm for all cases.

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.