CD
ну вот, для abc\0mbc\0xba и позиций 9, 1, 5 у тебя будет два lcp пары (9, 1) = 1 и пары (1, 5) = 2
Size: a a a
2020 May 26
CD
если тебе надо (9, 5) ты говоришь min((9, 1), (1, 5)) = min(1, 2) = 1
CD
просто range minimum
I
так постой
I
а тут разве считает количество раз, сколько встречается та или иная подстрока в строке?
CD
пока нет
CD
но ты для двух любых подстрок умеешь искать lcp
CD
а еще они упорядочены
CD
так что ты можешь найти диапазон всех индексов, которые равны данной подстроке данной строки
CD
а именно, для подстроки длины 5 тебе надо найти ближайшие индексы с отсчетами меньше 5 в массиве lcp соседних
I
Нууу, блин. Серьёзно, это я ещё не вкурил. Завтра напишу, разберу.
I
Но есть желание, сделать втупую.
CD
Нууу, блин. Серьёзно, это я ещё не вкурил. Завтра напишу, разберу.
Ну вот представь, тебе говорят, что соседний элемент суфмаса совпадает на первые 10 букав
CD
А следующий за ним на 8
CD
А следующий за ним на 11
CD
Это значит, что первый и четвертый совпадают на 8, так? :)
I
Да.
CD
ну вот, тебя теперь просят найти, сколько подстрок таких же, как с позиции первой, но длины 5
CD
четвертая точно в теме, она же на 8 совпадает
I
БП?