Поиск наибольшей общей подстроки у нескольких строк

[alliance]

Здравствуйте, нужно сделать поиск наибольшей общей подстроки у нескольких строк.
Реализовал суффиксное дерево, а что дальше - застопорился.
Посоветовали склеить строки a,b,c в одну с помощью символов не входящих в алфавит, получилось
 a#b$c@ , но вот что дальше - хз.
при строках a = "amaabcmabce", b = "menabrabc", c = "acabcdem"

при обходе в глубину получается

+      

•    "#menabrabc@acabcdem$"

+      [1]   "$"
+      [2]   "@acabcdem$"   
+      [3]   "aabcmabce#menabrabc@acabcdem$"   
+      [4]   "abc@acabcdem$"
+      [5]   "abcdem$"   
+      [6]   "abce#menabrabc@acabcdem$"   
+      [7]   "abcmabce#menabrabc@acabcdem$"   
+      [8]   "abrabc@acabcdem$"   
+      [9]   "acabcdem$"   
+      [10]   "amaabcmabce#menabrabc@acabcdem$"   
+      [11]   "bc@acabcdem$"   
+      [12]   "bcdem$"
+      [13]   "bce#menabrabc@acabcdem$"   
+      [14]   "bcmabce#menabrabc@acabcdem$"
+      [15]   "brabc@acabcdem$"
+      [16]   "c@acabcdem$"
+      [17]   "cabcdem$"
+      [18]   "cdem$"   
+      [19]   "ce#menabrabc@acabcdem$"   
+      [20]   "cmabce#menabrabc@acabcdem$"
+      [21]   "dem$"   
+      [22]   "e#menabrabc@acabcdem$"
+      [23]   "em$"   
+      [24]   "enabrabc@acabcdem$"
+      [25]   "m$"
+      [26]   "maabcmabce#menabrabc@acabcdem$"   
+      [27]   "mabce#menabrabc@acabcdem$"   
+      [28]   "menabrabc@acabcdem$"   
+      [29]   "nabrabc@acabcdem$"   
+      [30]   "rabc@acabcdem$"

а вот дальше - застой.

Кто-нибудь делал что-то похожее ?
спасибо

[Dimka]

alliance, и зачем скливать? Ты алгоритм опиши русским языком.

[alliance]

Прочитал на форуме, там советуют.
Построим по полученной строке суффиксный автомат. Для каждого состояния этого автомата определим, в каких строках оно встречается. Например, состояние встречается в строке A, если из этого состояния достижим переход по символу #. Аналогично, состояние встречается в строке B, если из него по переходам достижим переход по символу @ (но при условии, что при проверке достижимости мы не переходим по символу #). Аналогично, состояние встречается в строке C, если из него достижим переход по символу $ (при этом мы аналогично игнорируем переходы по символа # и @).

Я не понял, как таким образом можно определить наибольшую общую подстроку.

Состояний много, фактически мы просто перебираем состояния и смотрим, принадлежат ли они всем строкам вроде, но тогда по времени ппц получится, практически перебором

[Dimka]

alliance, я тоже не понял. Поэтому составь и опиши алгоритм, чем пытаться делать чужие советы, которые ты не понимаешь и пересказать не можешь.

Что касается перебора, то является ли эта задача NP-полной или нет, на вскидку не скажу. А ты, похоже, тем более не скажешь. Так что сначала представь хоть какое-то решение, а затем уже можно будет думать о его улучшениях и ускорениях.

В доску простое решение: получить из каждой строки множество всех возможных уникальных подстрок, а затем последовательно вычислять пересечение полученных множеств [ (...(S1 * S2) * S3 ... ) * Sn ]  подстрок. В результате выйдет множество всех общих подстрок, из которого останется выбрать самую длинную (или несколько одинакового размера).