Тема: Количество различных подстрок

Каким образом можно определить количество различных подстрок для строки длиной до 200 000?

2

Re: Количество различных подстрок

Динамикой по суффиксному дереву или суффиксному массиву.

3

Re: Количество различных подстрок

или автомату )

4

Re: Количество различных подстрок

Да, я хотел сказать по автомату)))
Как решать массивом не очень понятно

5

Re: Количество различных подстрок

Массивом тоже есть решение, но оно не самое простое. Щас попробую вспомнить smile Но, пожалуй, получится даже сложней, чем автомат написать )

6

Re: Количество различных подстрок

Сделать стандартный (за N log N) препроцессинг, который находит LCP для двух соседних в порядке сортировки суффиксов (т.е. если p[0..n-1] - перестановка суффиксов, сам суффиксный массив, то построим ещё массив lcp[0..n-2], lcp[i ] = lcp(p[i ], p[i+1])).

Тогда количество различных подстрок будет равно СУММЕ (n-p[i ]) - СУММА lcp[i ]. Действительно, будем рассматривать все суффиксы строки в порядке сортировки. Для каждого суффикса будем смотреть те его префиксы, которые дают новые подстроки. Суффикс p[0] даёт n-p[0] новых подстрок. Суффикс p[1] даёт n-p[1]-lcp[0] новых, потому что среди всех префиксов n-p[1] первые lcp[0] будут одинаковыми с нулевым шагом. И т.д.

7

Re: Количество различных подстрок

)) предыдущее решение я всегда пишу) но еще можно хешами))