CD
суфмассив, как и все суфструктуры, умеют все только по пребилду
Size: a a a
2020 May 26
I
abc\0mba
Имеем суфф мас
3, 6, 0, 5, 1, 2, 4
3, 6, 0, 5, 1, 2, 4
CD
ну там дальше доразбиваем до
3
6, 2
0, 4
5, 1
3
6, 2
0, 4
5, 1
I
И сужаем диапазон, как понимаю.
CD
ну там дальше доразбиваем до
3
6, 2
0, 4
5, 1
3
6, 2
0, 4
5, 1
вот у тебя суфмассивы построенные по отдельным позициям входных строк
I
Ага, тут сортировка по тому, как если бы у нас строки были бы в столбик записаны.
I
но, да, я не понимаю, что дальше. Но я сегодня весь день в работе, я думаю мне нужно время чтобы понять все.
CD
ну как только есть нужные суфмассивы, дальше автопилоты через lcp соседних
CD
у тебя для каждой пары соседних есть lcp, значит через rmq для любой пары есть lcp
CD
значит, для любой строки можно диапазон индексов суфмаса аналогичных выяснить через бинпоиск по lcp
I
значит, для любой строки можно диапазон индексов суфмаса аналогичных выяснить через бинпоиск по lcp
Ну, у меня строки не на вход поступают, они есть сразу, и вот среди них идёт счёт. Я подумаю, честно, мало понимаю. Выглядит конечно замудрено. Но, слова знакомые.
CD
ну смотри
CD
представь, что для каждой пары соседей в суфмассиве знаешь lcp
CD
там про это просто есть алгоритм
I
ну там дальше доразбиваем до
3
6, 2
0, 4
5, 1
3
6, 2
0, 4
5, 1
Ты про вертикальные пары?
CD
ну у тебя осталось что-то типа "0, 4"
I
это если две строки, а если их три, то будет
0, 4, 8
0, 4, 8
CD
I
Ну, это пара?
CD
я не очень уверен, что там амортизации не основаны на том, что это подстроки одной строки, но в любом случае ты это можешь узнать через тот же трюк с оригинальным суфмасом