Учитывая строку из n символов, скажем, «qqwqq», все возможные подстроки равны 11: qw-qq-qw-wq-qqw-qwq-wqq-qqwq-qwqq-qqwqq,
I упорядоченный массив суффиксов сформирован таким образом:
- Q 4
- QQ 3
- QQWQQ 0
- QWQQ 1
- WQQ 2
и взятый из него массив LCP:
Теперь, чтобы вычислить количество подстрок QQWQQ, я делаю все возможные подстроки (n * (n + 1) / 2) -> 15, минус сумма от 0 до n (- 1) массива LCP -> 4 для удаления дубликатов -> 15 - 4 = 11.
Если я хочу получить количество подстрок из строки в диапазоне (1, 3), то есть QWQ, есть ли способ получить это значение, используя тот же массив суффиксов и массив LCP, приведенный выше, без пересчета двух массивов для «новой» строки?
Я ожидаю, что это будет 5 : QW-QW-WQ-QWQ.
Спасибо.