Здравствуйте, у меня задача - построить наибольшую общую подстроку от 3х и более строк.
построил суффиксный автомат.
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$"
а вот дальше - застой.
Не до конца понял, что значит,
"Для каждого состояния этого автомата определим, в каких строках оно встречается. Например, состояние встречается в строке A, если из этого состояния достижим переход по символу #. Аналогично, состояние встречается в строке B, если из него по переходам достижим переход по символу @ (но при условии, что при проверке достижимости мы не переходим по символу #). Аналогично, состояние встречается в строке C, если из него достижим переход по символу $ (при этом мы аналогично игнорируем переходы по символа # и @)."