Количество отдельных подстроков в строке

Question

Из того, что я понял, лучшим способом его реализации является использование суффиксного массива $ S $ из строки $ w $ и его LCP-Array (самый длинный общий префикс) $ l $.

Ответ может быть получен

$$ sum_ {i = 1}^{| w |} left (| s [i] | -l [i -1] right). $$

Чего я не понимаю, так это как и почему это работает?

Я был бы очень благодарен, если бы кто -то это объяснил.

Answer 1

Вместо официального доказательства я хочу дать некоторую интуицию за формулой. Массив суффиксов содержит все суффиксы строки $ w $. Подстроение - это не что иное, как префикс суффикса. Так что, если вы считаете $ sum_i | s [i] | $, вы получите все подстроки, но, конечно другой подстроки.

Давайте поближе посмотрим. Предположим, что $ s [i-1] = xyz $ и $ s [i] = xyxyz $. По приведенным выше методу подсчета вход $ s [i-1] $ подсчитал подстроки $ x, xy $ и $ xyz $ и запись $ s [i] $ считать $ x, xy, xyx, xyxy, xyxyz $. Вы заметите, что, поскольку префиксы длины 2 обеих записей одинаковы, мы дважды подсчитывали $ x, xy $. Но длина самого длинного распространенного префикса хранится в $ l [i] $, поэтому мы вычитаем его, чтобы компенсировать переосмысление.