Here is the algorithm:
Input: a set of \$M\$ strings \$S=\{s_i\}\$ of length \$N\$ with alphabet \$\Sigma\$
Make an index of each string by chars. Maintain a position \$p=(p_i)\$ where \$p_i\$ is an index into string \$s_i\$. Set the initial position such that \$\forall i: p_i = |s_i|+1\$ (1-based indexing).
While chars left in strings do:
- Select the next point among matches (same char in every string) by looping through the alphabet shared by the strings and picking the point with the minimal m-dimensional euclidean distance to the current point.
Is this \$O(|\Sigma|*M*\log(N))\$?
Here is (quite bad) sample python code:
from collections import defaultdict
import sys, bisect
def mlcs(strings):
strings = list(set(strings))
indexes = dict()
sigma = set()
for x in strings:
sigma = sigma.union(set(x))
for x in strings:
tx = defaultdict(list)
for i in range(len(x)):
tx[x[i]] += [i]
indexes[x] = tx
def match(pos):
s = True
for i in range(len(strings)-1):
x = strings[i]
y = strings[i+1]
s &= x[pos[x]] == y[pos[y]]
return s
def distance(ind1, ind2):
d = 0
for x in strings:
d += (ind1[x] - ind2[x])**2
return d
def find(xs, y):
i = bisect.bisect_right(xs, y)
return i-1
pos = {}
for x in strings:
pos[x] = len(x)
result = ""
loop = True
while loop:
for x in strings:
if pos[x] < 0:
loop = False
if not loop:
break
indr = None
dr = 12777216
for c in sigma:
ind = defaultdict(int)
for x in strings:
indxc = indexes[x][c]
if indxc:
i = find(indxc, pos[x] - 1)
ind[x] = indxc[i]
if ind[x] > pos[x] - 1:
ind[x] = -128
else:
ind[x] = -128
d = distance(ind, pos)
if d < dr:
indr = ind
dr = d
x = strings[0]
def notnegative(p):
r = True
for x in p.values():
if x < 0:
r = False
return r
if notnegative(indr):
result = x[indr[x]] + result
pos = indr
return result
def check(string, seq):
i = 0
j = 0
while i < len(string) and j < len(seq):
if string[i] == seq[j]:
j += 1
i += 1
return len(seq) - j
def checkall(strings, seq):
for x in strings:
a = check(x, seq)
if not a == 0:
print(x, seq, a)
return False
return True
strings = []
sigma = ["a", "b", "c", "d"]
#sigma = ["a", "b"]
sigmax = ["e", "f", "g"]
import random
Nx = 67
N = 128
M = 13 # Number of strings
x = ""
for i in range(Nx):
x += random.choice(sigmax)
for i in range(M):
string = ""
for j in range(N):
string += random.choice(sigma)
indexes = list(range(N))
random.shuffle(indexes)
indexes = sorted(indexes[:len(x)])
for j in range(len(x)):
string = string[:indexes[j]]+x[j]+string[indexes[j]+1:]
strings += [string]
#strings = ["abbab", "ababa", "abbba"]
#strings = ["abab", "baba", "abaa"]
#strings = ["bacda", "abcde", "decac"]
#strings = ["babbabbb", "bbbaabaa", "abbbabab", "abbababa"]
print("Strings:", strings)
l = mlcs(strings)
print("Lcs:", l, len(l), checkall(strings, l))