1 Отредактировано 4a1ka (2012-01-26 10:08:55)

Тема: Наибольшая общая подстрока трех строк

Недавно прочитал статью для двух строк.
После этого наткнулся на задачу с тремя строками. Можно ли сделать это через суффиксный автомат?
Если да, то можете написать, нужно ли строить автомат для двух строк или для одной хватает, и как после этого искать подстроку?

2

Re: Наибольшая общая подстрока трех строк

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

Посчитав теперь эти достижимости (что можно делать за линейное время - с помощью динамического программирования с меморизацией или оформив это в виде обхода в глубину), мы просто выбираем в качестве ответа такое состояние, которое лежит во всех трёх строках, и при этом имеет наибольшую длину length. (Чтобы вывести саму искомую подстроку, а не только её длину, вместе с каждым состоянием автомата надо будет хранить позицию endpos - она упоминается в статье.)

Re: Наибольшая общая подстрока трех строк

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

4

Re: Наибольшая общая подстрока трех строк

Надо найти такую вершину v, у которой st[v].len максимально, и при этом из этой вершины есть путь, содержащий @ (но не #$), есть путь, содержащий # (но не @$), и есть путь, содержащий, $ (но не @#).

5 Отредактировано freele (2012-06-28 15:51:41)

Re: Наибольшая общая подстрока трех строк

Здравствуйте.
Та же задача.
Сделал суффиксный автомат, и общая подстрока ищется при проходе по буквам, но это медленный метод.
Пробую организовать проход по инвертированным суффиксным ссылкам, чтобы обойтись за время O(n). Но в таком случае я не понимаю, как проверить, находясь в каком-либо узле, есть ли у него путь, содержащий разделитель.
Я уже кучу версий перепробывал. Или это нужно как-то учесть при построении автомата? Или нужно автомат превратить в дерево?
Не могу понять, как проверить путь, если двигаться не по буквенным ссылкам автомата, которые этот путь и определяют.

6

Re: Наибольшая общая подстрока трех строк

Ещё раз, мы склеиваем три строки через три разделителя, строим по получившейся строке суффиксный автомат. Далее для каждого состояния автомата обходом в глубину (или динамикой с меморизацией, как угодно называть) мы находим три булевских величины: path_exists_1, path_exists_2, path_exists_3, где path_exists_i означает "из текущей вершины есть путь, заканчивающийся символом, равным разделителю номер i, и при этом не содержащий других разделителей".

После этого ответом на задачу будет просто состояние v, для которого все три величины равны true (точнее, искомая подстрока будет длиннейшим путём из истока в это состояние v).

7 Отредактировано freele (2012-06-28 16:23:00)

Re: Наибольшая общая подстрока трех строк

Логику я понимаю. И деление, обход, все понятно.
Не ясно, как, делая обход по суффиксным обратным ссылкам в глубину, определить наличие пути по символу из узла.

Вот лог обхода с номером состояния, строкой и ссылками перехода.
2 строки: aba, zab, разделители - цифры.

v: 0
   longest: 
1 2 4 5 8 
v: 1
   longest: a
3 6 
v: 3
   longest: aba

v: 6
   longest: aba0za

v: 2
   longest: ab
7 
v: 7
   longest: aba0zab

v: 4
   longest: aba0

v: 5
   longest: aba0z

v: 8
   longest: aba0zab1

Как двигаясь по этим ссылкам, определить наличие пути? Или я не так что-то сделал?
Я уже от корки до корки перечитал статьи - про автомат со всеми задачами, найти наибольшую повторяющуюся подстроку оказалось несложно, с двумя тоже все легко. Но я застопорился на том, как определить путь из узла проходом в глубину, двигаясь по суффиксным ссылкам (обратным).

8

Re: Наибольшая общая подстрока трех строк

Нет-нет-нет, не надо никаких обратных суффиксных ссылок smile
Мы просто просматриваем рёбра, выходящие из каждого состояния.
Скажем, чтобы найти наличие пути из состояния v = 0, мы просматриваем рёбра, исходящие из состояния v = 0 в другие состояния, и использовать ответы, уже посчитанные для них.

9

Re: Наибольшая общая подстрока трех строк

Но ведь в таком случае я , возможно, буду в каждое состояние заглядывать не 1 раз, а это может замедлить программу. Разве не так? Или полученный суффиксный автомат нужно было как-то преобразовать?

10

Re: Наибольшая общая подстрока трех строк

Ну суффиксный автомат ацикличен, поэтому при подсчёте path_exists_i для текущего состояния мы можем считать, что для всех состояний, в которые есть рёбра из текущего состояния, всё уже посчитано. Поэтому мы можем просто брать ответы для них, а глубже уже не заходить.

11

Re: Наибольшая общая подстрока трех строк

Большое спасибо, за статьи и за ответ.
Попробую это обдумать.
А если ребер нет, то и не проверять. То есть можно флаг "проверено" сделать для узла, и не заходить 2-й раз. Не усложняю?

12

Re: Наибольшая общая подстрока трех строк

Ну да, сделать какой-то флаг "величины path_exists_i" посчитаны, и если этот флаг стоит - то ничего для этого узла делать больше не надо. Это и называется "ленивым динамическим программированием" - когда мы вычисляем какие-то величины при первом требовании.

13

Re: Наибольшая общая подстрока трех строк

Кто-нибудь подскажите как именно в суф. автомате можно обойти эти рёбра чтоб пробить для каждого состояния необходимые флаги, без использования рекурсии. Ну и чтоб многократно не проходить всё дерево несколько раз. Третий день пытаюсь разобраться, чёт не получается... не пойму над идти по линкам, или по значениям с индексами нужных символов или вообще как?

14

Re: Наибольшая общая подстрока трех строк

Подскажите пожалуйста как можно увеличить быстродействие алгоритма при обходе в длинну. Уже сделано: помечаю флагами все автоматы на пути от текущего до спецсимвола и не считаю их в дальнейшем, помечаю флагами автоматы при построении, когда к нему подсоединяют ребро со спецсимволом.  Даже после этих действий время работы программы недостаточно. Нужно добиться 1 секунды для 10 строк в которых может быть до 10000 символов. Сейчас время работы примерно 3-4 секунды.

15

Re: Наибольшая общая подстрока трех строк

Xardas пишет:

Подскажите пожалуйста как можно увеличить быстродействие алгоритма при обходе в длинну. Уже сделано: помечаю флагами все автоматы на пути от текущего до спецсимвола и не считаю их в дальнейшем, помечаю флагами автоматы при построении, когда к нему подсоединяют ребро со спецсимволом.  Даже после этих действий время работы программы недостаточно. Нужно добиться 1 секунды для 10 строк в которых может быть до 10000 символов. Сейчас время работы примерно 3-4 секунды.

Получилось ли тогда доделать задачу?
//Интересно, Яндекс всегда дает одни и те же задачи?

16 Отредактировано epicgoods (2013-05-30 14:47:01)

Re: Наибольшая общая подстрока трех строк

Толи я чего-то не понимаю, но для составной подстроки: a1b2
построив СА

Array
(
    [0] => Array
        (
            [len] => 0
            [link] => -1
            [next] => Array
                (
                    [a] => 1
                    [1] => 2
                    [b] => 3
                    [2] => 4
                )

        )

    [1] => Array
        (
            [len] => 1
            [link] => 0
            [next] => Array
                (
                    [1] => 2
                )

        )

    [2] => Array
        (
            [len] => 2
            [link] => 0
            [next] => Array
                (
                    [b] => 3
                )

        )

    [3] => Array
        (
            [len] => 3
            [link] => 0
            [next] => Array
                (
                    [2] => 4
                )

        )

    [4] => Array
        (
            [len] => 4
            [link] => 0
        )

)

мы получим достижимости из узлов 1,2,3 для перовго разделителя(1) и 1,3,4 - для второго(2). Далее казалось бы нужно построить суффикс для узла 3? Что уже наверное неправильно, так длина суффикса в этой вершине 3, а мы явно видим, что здесь нет общей строки. Я хотел было сначала составлять суффикс, перебирая все вершины для поиска ребер за исключением разделителей и уменьшая длину len за итерацию, однако в этом я тоже не уверен.

Помощь нужна срочно)