On the Complexity of Finding Approximate LCS of Multiple Strings

Hamed Hasibi, Neerja Mhaskar, W. F. Smyth

Finding an Approximate Longest Common Substring (ALCS) within a given set $S=\{s_1,s_2,\dots ,s_m\}$ of $m\ge 2$ strings is a key problem in computational biology, such as identif…