A Heuristic Algorithm for the N-LCS Problem 1
Mourad Elloumi, Ahmed Mokaddem · 2010
Let f={w1, w2, …,wN} beasetofN strings, a string s is an N-Common Subsequence (N-CS) of f, ifandonlyif, s is a subsequence of each of the N strings of f. Hence, the N-Longest Common Subsequence (N-LCS) problem is defined as follows: Given a set of N strings f={w1, w2, …,wN} findanN-CS of f of maximum length. When N>2, the N-LCS problem becomes NP-hard [Maier 78] and even hard to be approximated [Jiang and Li 95]. In this paper, we present A heuristic algorithm, adopting a regions approach, for the N-LCS problem, where N�2. Our algorithm is O(N*L*log(L)) in computing time, where L is the maximum length of a string. During each recursive call to our algorithm: We look for the longest common substrings that appear in the different strings. If we have more than one longest common substring, we do a filtering.