Тема: Количество различных подстрок
Каким образом можно определить количество различных подстрок для строки длиной до 200 000?
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » Количество различных подстрок
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Каким образом можно определить количество различных подстрок для строки длиной до 200 000?
Динамикой по суффиксному дереву или суффиксному массиву.
Да, я хотел сказать по автомату)))
Как решать массивом не очень понятно
Массивом тоже есть решение, но оно не самое простое. Щас попробую вспомнить Но, пожалуй, получится даже сложней, чем автомат написать )
Сделать стандартный (за 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] будут одинаковыми с нулевым шагом. И т.д.
)) предыдущее решение я всегда пишу) но еще можно хешами))
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » Количество различных подстрок