Может кто-нибудь помочь мне с этим вопросом: Это не домашняя работа, я готовлюсь к техническому собеседованию.
Учитывая серию из N строк, найдите набор повторяющихся строк размером 3, например, ababadefb
Простым решением было бы создать массив суффиксов из строки, отсортировать его и вычислить самый длинный общий префикс между текущим и предыдущим суффиксами. Теперь все LCP длиной 3 или более дадут вам ответ (аба в данном случае).
ababadefb 0 abadefb 3 adefb 1 b 0 babadefb 1 badefb 2 defb 0 efb 0 fb 0
В качестве альтернативного решения вы можете построить Дерево корней из всех суффиксов, а затем получить все ребра, помеченные строками длиной 3 или более.
Я думаю, что мы могли бы страдать от незнания всей проблемы. Я собираюсь направить вас к записи в блоге моего друга, где он рассказывает о своем интервью с Microsoft .